Haskell length function execution
I am starting to learn Haskell programming and am trying to understand the structure of a list, so I wrote a list length function.
myLength :: [a] -> Integer
myLength = foldr (\x -> (+) 1) 0
myLength1 :: [a] -> Integer
myLength1 [] = 0
myLength1 (x:xs) = (+1) (myLength1 xs)
Above are 2 length functions. my question is which one is better? from my point of view, myLength1 is much better understood, and looks natural for a list of operations.
But myLength looks shorter and doesn't use recursion, does that imply myLength is faster than myLength
source to share
Notice this "pseudo-implementation" foldr
:
foldr :: function -> initializer -> [a] -> b
foldr _ i [] = i
foldr f i (x:xs) = x `f` (foldr f i xs)
We now have the code
myLength :: [a] -> Integer
myLength = foldr (\x -> (+) 1) 0
myLength1 :: [a] -> Integer
myLength1 [] = 0
myLength1 (x:xs) = (+1) (myLength1 xs)
Since it's foldr
also recursive, your myLength1 and myLength will be pretty much the same, but in the first case, the recursive call is done using foldr instead of explicitly. They should be running around the same time.
source to share
Both functions do the same: foldr use recursion and end up like your straight recursive function. One could argue that the foldr version is cleaner (once you get used to it, a higher-order function is often more readable than direct recursion).
But these two functions are pretty bad: they will both get a large chunk (invaluable) 1 + (1 + (1 + ... + 0)..))
, which will take up a lot of memory (O (n) space) and will slow down the evaluation. To avoid this, you should start adding 1s from the beginning of the list, for example:
betterLength xs = go 0 xs
where
go n [] = n
go n (_:xs) = n `seq` go (n+1) xs
seq
ensures that n is evaluated before the go function is called recursively and therefore no accumulation +1
. With an extension, BangPatterns
you can write this:
betterLength xs = go 0 xs
where
go n [] = n
go !n (_:xs) = go (n+1) xs
You can also make this folded version:
betterLength = foldl' (\n _ -> n + 1) 0
where foldl'
starts with l eft and strictly ( ' ).
source to share