Stefan Höck schreef op 10-11-2014 20:47:

Let's do this step by step. We use the following list: [1,2,3]

foldr takes three arguments:

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

The last of the three has type [a]. This means, the fold expects a list as an argument here. The lower case letter `a` is the type of the items in the list. In our case this is `Int`, but we could pass it other lists with other element types.

The second argument of the fold has type `b`, this is the result type we'd like to get from the fold. In our case this is `Maybe Int` since we want to know from the result, whether the list was empty or not. Nothing in case of an empty list, Just x with x being the right-most item in the non-empty case.

The first argument of the fold is a higher order function. It accepts an argument of type `a` (the element type of the list) and of type `b` (the result type of the fold) and should return a value of type `b`. In our example, `a` is equal to `Int` and b is equal to `Maybe Int`.

Therefore, the following cannot possibly work:

...

acc a acc = if null a then Nothing else if (null (tail a)) then (Just

the first argument of acc (the value `a` in your implementation) has type `a` (note the distinction between a value and a type, both have the same name here, but that doesn't need to be the case. You could rename the value to x or foo or whatever). In our case, the type `a` is `Int` since we fold over a list of Ints. If we were to fold over a list of Strings, type `a` would be equal to `String`. Note however, that since `a` can be anything (Int, String etc, depending on the element type of your list), you cannot possibly call `null` on it. null takes a list as an argument, but `a` is not necessarily a list. It's the type of the list's elements, not the whole list. You do not pass the whole list to the accumulator. You only pass it the list's element in single file.

Now, what happens, when we fold over the list? Since we fold from the right, our accumulator is passed two arguments: The last value of the list and the initial value of type `b` (in our case `Nothing`).

acc 3 Nothing = ???

What should be the result of this? Clearly you'd like to keep the 3 as it is actually the result you are looking for. But you cannot return the 3 directly. The return type of our function must be `Maybe Int` and the type of `3` is `Int`. We first must wrap the `3` in a `Maybe`. There is only one way to do that:

acc 3 Nothing = Maybe 3

(This is pseudocode an will not compile. The real implementation follows below)

Now comes the next item in the list: `2`. Function acc gets called again, this time with `2` as its first argument, and the result of our fold so far which is `Just 3`

acc 2 (Just 3) = ???

Clearly we do not want to lose the `3`, it's the result we are looking for after all!

acc 2 (Just 3) = Just 3

Finally, the last item (from the right) in the list comes along:

acc 1 (Just 3) = Just 3

Again we let it pass and get Just 3 as the result.

This is how foldr works. Every element of the list starting with the rightmost is passed as an argument to the accumulator function together with the value accumulated so far (for which you must provide an initial value).

Now, the implementation. We have seen, that we want to get hold of the very first value that comes from the list and ignore everything else that comes after it.

acc :: a -> Maybe a -> Maybe a # This is the function's type signature acc x Nothing = Just x # We wrap the first value ... acc x (Just y) = Just y # and keep hold of it

When we now use this accumulator in our fold, it gets first called with arguments `3` and `Nothing` so the first pattern matches. Variable x is assigned the value `3` and the result is `Just 3`.

The function gets called again with the second value `2` and `Just 3`, the result from the first call. This time, the first pattern does not match (Nothing does not match `Just 3`), but the second does. `x` is assigned the value `2`, `y` is assigned the value `3` (the one wrapped in the `Just`) and the result is `Just 3`. Same for the last element.

Here is the complete implementation:

last5 :: [a] -> Maybe a last5 = foldr acc Nothing where acc x Nothing = Just x acc x (Just y) = Just y

Or better

last5 :: [a] -> Maybe a last5 = foldr acc Nothing where acc x Nothing = Just x acc _ j = j

Or even (this one will be harder to figure out) last5 :: [a] -> Maybe a last5 = foldr acc Nothing where acc x = maybe (Just x) Just

Cheers, Stefan

I understand the theory but i loose it on the implementation. Lets take the better variant. last5 :: [a] -> Maybe a last5 = foldr acc Nothing where acc x Nothing = Just x acc _ j = j Let's say we have [1,2,3] Do I understand that acc = Nothing. and x = 3 ? and after acc x Nothing = Just x acc get's the value 3 But how does x get's the value 3 or does foldr takes care of that ? Roelof

Thanks, I think my error in thinking is that most of the languages store values in a variable, But it seems that haskell do not use it in a fold Roelof Stefan Höck schreef op 10-11-2014 21:15:

...

I understand the theory but i loose it on the implementation.

Lets take the better variant.

last5 :: [a] -> Maybe a last5 = foldr acc Nothing where acc x Nothing = Just x acc _ j = j

Let's say we have [1,2,3]

Do I understand that acc = Nothing. and x = 3 ? Not, acc is not Nothing. acc is a function of type (a -> Maybe a -> Maybe a). Nothing is a value of type Maybe a. The two cannot possibly be the same. foldr takes care of feeding the proper arguments to `acc`.

...

and after acc x Nothing = Just x acc get's the value 3 The result of calling `acc` with arguments 3 and Nothing is `Just 3`. But that's NOT the value of `acc`. acc is still a function. Note that there is no such thing as in-place mutation in Haskell, so you cannot just change the value of `acc`. But the RESULT of calling

acc 3 Nothing

is `Just 3`. This result is taken by foldr and passed again to `acc` together with the next item in the list. This continues until the list is exhausted and foldr returns the last result it got from calling `acc`.

...

But how does x get's the value 3 or does foldr takes care of that ? foldr takes care of all that. foldr calls `acc` with the proper arguments and does all the bookkeeping internally. There is actually not much to bookkeep. Here's an implementation of foldr

foldr :: (a -> b -> b) -> b -> [a] -> b foldr _ b [] = b foldr f b (a:as) = foldr f (f a b) as

So, no great bookkeeping, just plain recursion.

Stefan _______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

It's an indentation issue. Make sure that there are no spaces before the bit about 'last5 = foldr acc' etc. On Mon, Nov 10, 2014 at 12:48 PM, Roelof Wobben wrote:

Roelof Wobben schreef op 10-11-2014 20:59:

...

last5 :: [a] -> Maybe a last5 = foldr acc Nothing where acc x Nothing = Just x acc _ j = j

When I enter this in GHCI I see this error :

Illegal type signature: ‘[a] -> Maybe a last5’

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

_ just means "ignore this parameter, I'm not going to use it" On Tuesday, November 11, 2014, Roelof Wobben wrote:

Thanks, this is working well.

But just for understanding

in the part acc x Nothing x is the input string, and in the part _j means the same as (xs:x)

Roelof

Alex Hammel schreef op 10-11-2014 22:47:

It's an indentation issue. Make sure that there are no spaces before the bit about 'last5 = foldr acc' etc.

On Mon, Nov 10, 2014 at 12:48 PM, Roelof Wobben javascript:_e(%7B%7D,'cvml','r.wobben@home.nl');> wrote:

...

Roelof Wobben schreef op 10-11-2014 20:59:

...

last5 :: [a] -> Maybe a last5 = foldr acc Nothing where acc x Nothing = Just x acc _ j = j

When I enter this in GHCI I see this error :

Illegal type signature: ‘[a] -> Maybe a last5’

_______________________________________________ Beginners mailing list Beginners@haskell.org javascript:_e(%7B%7D,'cvml','Beginners@haskell.org'); http://www.haskell.org/mailman/listinfo/beginners

_______________________________________________ Beginners mailing listBeginners@haskell.org javascript:_e(%7B%7D,'cvml','Beginners@haskell.org');http://www.haskell.org/mailman/listinfo/beginners

-- Sent from an iPhone, please excuse brevity and typos.

The program traverses the list from right to left. The first element that acc sees during traversal is the last element of the list. The idea is as follows: Parameter y is the partial calcresult. If y (in your code) is Nothing then acc returns Just x. So the new partial result is the current list element in a Just. The next time acc is called, y is not Nothing but a Just. In that case acc returns the partial calcresult unchanged. So, y is Nothing for the last list element and Just <last element of the list> for all other list elements. last5 :: [a] -> Maybe a last5 xs = foldr acc initial xs acc :: a -> Maybe a -> Maybe a acc x Nothing = Just x acc _ aJust = aJust initial :: Maybe a initial = Nothing In your code you don’t need the ‘where’ in the acc definition. Define acc for Nothing and for Just. Kees --------------- Im now trying to make a rfold solution to this problem. Till now I have this : last5 :: [a] -> Maybe a last5 xs = foldr acc initial xs acc :: a -> Maybe a -> Maybe a acc x y = where     acc x Nothing  = Just x     acc _ j        = j initial :: Maybe a initial = Nothing So still not working. Can someone explain to me in small steps how to figure out what the right answer is to the acc part. Roelof Roelof Wobben schreef op 11-11-2014 8:20: Thanks, this is working well. But just for understanding in the part acc x Nothing   x is the input string, and in the part _j means the same as (xs:x) Roelof   Alex Hammel schreef op 10-11-2014 22:47: It's an indentation issue. Make sure that there are no spaces before the bit about 'last5 = foldr acc' etc. On Mon, Nov 10, 2014 at 12:48 PM, Roelof Wobben wrote: Roelof Wobben schreef op 10-11-2014 20:59: last5 :: [a] -> Maybe a    last5 = foldr acc Nothing where        acc x Nothing  = Just x        acc _ j        = j When I enter this in GHCI  I see this error : Illegal type signature: ‘[a] -> Maybe a last5’ _______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners _______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

I used to have a blog (well I still do), but it was about functional reactive programming in Scala. I'm actually quite a noob in Haskell myself but with some experince in functional programming in Scala. There is a Scala library called 'scalaz' which was inspired by all the cool concepts found in Haskell and Cathegory Theory and I learned lots of stuff there. Nowadays, two little children keep me busy. No time for blogs. :-) On Tue, Nov 11, 2014 at 02:05:52AM +0900, Dontdie YCH wrote:

Another noob here.

Thanks for this step by step guide. Your writing style is very attractive.

Do you have blog about Haskell or any programming subject ?

Thanks.