On Sun, Feb 05, 2012 at 01:56:20AM +0100, Ralf Hemmecke wrote:
> On 02/04/2012 06:13 PM, Serge D. Mechveliani wrote:
>> [..]
>>>> dropWhile(p: Character -> Boolean, xs: List Character) :
>>>> List Character ==
>>>> empty? xs => xs
>>>> p first(xs) => dropWhile(p, rest xs)
>>>> xs
>>>> Is this more efficient?
>
> In the list case I guess using a loop instead of recursive call is a
> little more efficient.
>
> LC ==> List Character
> dropWhile(p: Character -> Boolean, xs: LC): LC ==
> while not empty? xs and p first xs repeat xs := rest xs
> xs
> [..]
These all things looks rather unusual to me.
Well, I knew that in C a recursion with a function call costs considerably
more than an ordinary loop.
But in Haskell, people do not think of such details. First, because
there is no plain possibility to write a loop as above.
Second -- for the sake of a plain style.
Third -- because this is a matter of a compiler. Under -O, some compilers
(like Glasgow Haskell) inline the body of each simple enough function
and produce the optimized code. In particular, the library functions
`head' and `tail' will be in-lined, and so on.
Though, I doubt greatly that the optimized result code for the above
example will be free of a recursive call for something which stands for
dropWhile.
I shall find out how to see the C code made by Glasgow Haskell.
But meanwhile, here is the assembly code (i386-unknown-Linux) for
module TT (dropCWhile)
where
dropCWhile :: (Char -> Bool) -> [Char] -> [Char]
dropCWhile p xs = case xs of [] -> []
x: ys -> if p x then dropCWhile p ys
else xs
It is by gcc -O2 -S TT.hs, after applying Gnu C
(for Intel(R) Pentium(R) 4 Mobile):
-- TT.s ----------------------------------------
.data
.align 4
.align 1
.globl __stginit_TT
.type __stginit_TT, @object
__stginit_TT:
.data
.align 4
.align 1
.globl TT_dropCWhile_closure
.type TT_dropCWhile_closure, @object
TT_dropCWhile_closure:
.long TT_dropCWhile_info
.text
.align 4,0x90
.long 3
.long 32
sam_info:
.LcaE:
movl %esi,%eax
andl $3,%eax
cmpl $2,%eax
jae .LcaF
movl 12(%ebp),%esi
addl $16,%ebp
andl $-4,%esi
jmp *(%esi)
.LcaF:
movl 4(%ebp),%eax
movl %eax,12(%ebp)
addl $8,%ebp
jmp TT_dropCWhile_info
.size sam_info, .-sam_info
.text
.align 4,0x90
.long 66
.long 32
sak_info:
.LcaP:
movl %esi,%eax
andl $3,%eax
cmpl $2,%eax
jae .LcaQ
movl $ghczmprim_GHCziTypes_ZMZN_closure+1,%esi
addl $12,%ebp
jmp *0(%ebp)
.LcaQ:
movl 6(%esi),%eax
movl %eax,0(%ebp)
movl %esi,8(%ebp)
movl 2(%esi),%eax
movl %eax,-8(%ebp)
movl 4(%ebp),%esi
movl $sam_info,-4(%ebp)
addl $-8,%ebp
jmp stg_ap_p_fast
.size sak_info, .-sak_info
.text
.align 4,0x90
.long 131084
.long 0
.long 15
.globl TT_dropCWhile_info
.type TT_dropCWhile_info, @object
TT_dropCWhile_info:
.LcaY:
leal -12(%ebp),%eax
cmpl 84(%ebx),%eax
jb .Lcb0
movl 4(%ebp),%esi
movl $sak_info,-4(%ebp)
addl $-4,%ebp
testl $3,%esi
jne sak_info
jmp *(%esi)
.Lcb0:
movl $TT_dropCWhile_closure,%esi
jmp *-4(%ebx)
.size TT_dropCWhile_info, .-TT_dropCWhile_info
.section .note.GNU-stack,"",@progbits
.ident "GHC 7.4.1"
-----------------------------------------------------------------
I wonder whether it contains some representation for a recursive function
call for the C image of dropCWile
(may be .LcaQ: pushes the registers to stack before something, I do not
remember this assembly issues).
Regards,
------
Sergei
[email protected]
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/fricas-devel?hl=en.
