CODEWITHSUNDEEP
haskellanonymous-functionfold
Andi Smith
Andi Smith

Reputation: 33

Haskell Fold with anonymous function

I have a problem with one of the Haskell basics: Fold + anonymous functions

I'm developing a bin2dec program with foldl.
The solution looks like this:

bin2dec :: String -> Int
bin2dec = foldl (\x y -> if y=='1' then x*2 + 1 else x*2) 0

I understand the basic idea of foldl / foldr but I can't understand what the parameters x y stands for.

Upvotes: 3

Views: 6102

Answers (2)

Satvik
Satvik

Reputation: 11208

See the type of foldl

foldl :: (a -> b -> a) -> a -> [b] -> a

Consider foldl f z list

so foldl basically works incrementally on the list (or anything foldable), taking 1 element from the left and applying f z element to get the new element to be used for the next step while folding over the rest of the elements. Basically a trivial definition of foldl might help understanding it.

 foldl f z []     = z
 foldl f z (x:xs) = foldl f (f z x) xs

The diagram from Haskell wiki might help building a better intuition.

foldl f z

Consider your function f = (\x y -> if y=='1' then x*2 + 1 else x*2) and try to write the trace for foldl f 0 "11". Here "11" is same as ['1','1']

  foldl f 0 ['1','1'] 
= foldl f (f 0 '1') ['1']

Now f is a function which takes 2 arguments, first a integer and second a character and returns a integer. So In this case x=0 and y='1', so f x y = 0*2 + 1 = 1

= foldl f 1 ['1']
= foldl f (f 1 '1') []

Now again applying f 1 '1'. Here x=1 and y='1' so f x y = 1*2 + 1 = 3.

= foldl f 3 []

Using the first definition of foldl for empty list. 

= 3

Which is the decimal representation of "11".

Upvotes: 7

Chris Taylor
Chris Taylor

Reputation: 47382

Use the types! You can type :t in GHCi followed by any function or value to see its type. Here's what happens if we ask the for the type of foldl

Prelude> :t foldl
foldl :: (a -> b -> a) -> a -> [b] -> a

The input list is of type [b], so it's a list of bs. The output type is a, which is what we're going to produce. You also have to supply an initial value for the fold, also of type a. The function is of type

a -> b -> a

The first parameter (a) is the value of the fold computed so far. The second parameter (b) is the next element of the list. So in your example

\x y -> if y == '1' then x * 2 + 1 else x * 2

the parameter x is the binary number you've computed so far, and y is the next character in the list (either a '1' or a '0').

Upvotes: 2

Related Questions