[Haskell-beginners] Are these soloutions all valid and a good use of Haskell

[Stefan Höck]

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


On Mon, Nov 10, 2014 at 06:28:46PM +0100, Roelof Wobben wrote:
>    oke,
>    I try it with this :
>    acc :: a -> Maybe a -> Maybe a
>    acc a acc  = if null a then Nothing else if (null (tail a)) then (Just
>    acc) else acc  a acc
>    else
>    if the tail a  is empty so there is only 1 item then the output must be
>    acc
>    else
>    must be run again ( there is a list with more then 1 item)
>    but now I see this error message :
>    Couldn't match expected type ‘a -> Maybe a -> Maybe a’ with actual type
>    ‘Maybe a’ Relevant bindings include acc :: Maybe a
>    and that is on the else part
>    Roelof
>    Benjamin Edwards schreef op 10-11-2014 18:07:
> 
>    > It is complining but as soon as I want to run it , I see this message
>    :
>    > Non-exhaustive patterns in function acc
> 
>      Yep, Maybe has two constructors, and you are only handling one. You
>      should handle the Nothing case as well.
> 
> _______________________________________________
> Beginners mailing list
> [1]Beginners at haskell.org
> [2]http://www.haskell.org/mailman/listinfo/beginners
> 
> References
> 
>    1. mailto:Beginners at haskell.org
>    2. http://www.haskell.org/mailman/listinfo/beginners

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