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

[Stefan Höck]

> I try to say that if the input list has only 1 item the outcome is the head
> of that list.

This is not how one typically thinks about folds. Look at the type of
acc:

  acc :: a -> Maybe a -> Maybe a

acc is a function wich takes two arguments (ignoring currying): On is of
type `a`. This is the element type of the list you fold over. The other
is of type `Maybe a`. This is the value you accumulate in your fold.
The initial value is `Nothing`. You start your fold literally with
nothing, since you haven't visited any element in the list yet. Now the
first element of the list (see below) is passed to acc. What do you do
with it?

  acc a Nothing = ???

a is an element in your lit, Nothing is the value you have accumulated
so far. What do you do? Ignore a? Keep it? If you ignore a, you return
`Nothing`.

  acc a Nothing = Nothing

With this accumulator, the list will be traversed (ignoring lazy
evaluation for the time being), all values will be
ignored and your result will be Nothing, no matter what kind of list you
fold over. Therefore, let's keep value `a`. In order to do that, we have
to wrap it in a Just, otherwise the types won't match:

  acc a Nothing = Just a

This function will give the right result for empty lists (Nothing) and
for lists with a single value where the value is wrapped in a Just. The
function will throw an error however, if you pass it a list containing
more than one element, because the pattern match is not exhaustive.
We need to decide what happens, when we already have a
value wrapped in a Just:

  acc a Just b = ???

Here you have three possibilities. a) return Just b, b) return Just a,
c) return Nothing. These are all the options you have. Anything else
(except for throwing errors) will not compile. You can try each of the
three. One will give you the head of the list, one will give you the
last item of the list, and one will give you Nothing for lists with more
than one element.

Note that the result of your function depends on which fold you use.
foldl folds from the left. The first element passed to the accumulating
function will be the head of the list. foldr folds from the right.
The first value passed to the accumulating function is the last in the
list.

So, think about the fold like this: Every element of the list is passed
to your accumulator and each time you must decide whether you want to
keep it or let it pass. If you keep them all, you will in the end hold
the last element passed to your accumulator. If you let them all pass
(except for the first, which you keep since you still have Nothing),
you will end up with the first element passed to you. If you fold
from the right, the first element you get is the last in the list. Keep
it and don't let it go. If you fold from the left, the first element
will be the head of the list. Throw them all away except for the very last
one.

Feel free to ask, if this doesn't make sense.

Stefan

> Stefan Höck schreef op 10-11-2014 15:23:
> >Just a quick note: That's 'typed holes' not 'type holes' ...
> >
> >On Mon, Nov 10, 2014 at 03:12:20PM +0100, Stefan Höck wrote:
> >>Hi Roelof
> >>
> >>It seems like you try to do too many things at once. Here's how you
> >>could go about this step-by-step and let GHC help you implement your
> >>functions along the way:
> >>
> >>First, give the type signature of your function:
> >>
> >>   last5 :: [a] -> Maybe a
> >>   last5 = undefined
> >>
> >>Now, load this into GHCi or compile with GHC. If it compiles, you're
> >>on the right track. Now, you want to implement it using a fold
> >>(try both, foldl and foldr):
> >>
> >>   last5 :: [a] -> Maybe a
> >>   last5 xs = foldr _ _ xs
> >>
> >>The underscores are 'type holes'. This tells the compiler to give you
> >>some information about what is supposed to be placed at the two
> >>positions. For the moment, we are only interested in the types of the
> >>things that go there. The compiler will tell you, that
> >>the hole at the first position is of type
> >>
> >>   a -> Maybe a -> Maybe a
> >>
> >>and the hole at the second position is of type
> >>
> >>   Maybe a
> >>
> >>Now, instead of filling the holes in place, let's define two helper
> >>functions together with their type signatures. You can later on inline
> >>them in your definition of last5, but for the time being, let's get as
> >>much help from the compiler as we can.
> >>
> >>   last5 :: [a] -> Maybe a
> >>   last5 xs = foldr acc initial xs
> >>
> >>   acc :: a -> Maybe a -> Maybe a
> >>   acc = undefined
> >>
> >>   initial :: Maybe a
> >>   initial = undefined
> >>
> >>Again, compile or load into GHCi. If you did anything wrong, the
> >>compiler will tell you so. There is only one possible way to
> >>implement function `initial` without cheating (= raising an error)
> >>
> >>   initial :: Maybe a
> >>   initial = Nothing
> >>
> >>Function `acc` can be implemented in several ways. Only one of them
> >>will lead to the desired behavior. Finding out the proper implementation
> >>is the main point of this folding-exercise. Try also an implementation
> >>using foldl. Does it behave as expected? What are the differences
> >>compared to foldr?  When you feed your implementations a huge list -
> >>say [1..20000000] - what happens?
> >>
> >>Note that whenever you get an error message in a rather complex
> >>function implementation, move local function definitions and lambdas
> >>to the top level, give them a type signature and implement them
> >>separately one at a time. Use type holes to let the compiler give
> >>assistance with type signatures and possible implementations.
> >>Once everything compiles and runs as expected, move the toplevel
> >>definitions back to where you'd like them best.
> >>
> >>Stefan
> >>
> >>PS: A more succint implementation of last5 would use currying:
> >>
> >>     last5 = foldr acc initial
> >>
> >>PPS: If you get a stack overflow with very large lists, try
> >>      using foldl' from Data.List (or better, once you learned
> >>      about the Foldable type class, from Data.Foldable).
> >>
> >>On Mon, Nov 10, 2014 at 02:28:08PM +0100, Roelof Wobben wrote:
> >>>I tried and so far I have this :
> >>>
> >>>last5 = foldl(\acc x -> if x=[] then x else acc xs) [] xs
> >>>
> >>>But now I get parse error on the -> part.
> >>>
> >>>Roelof
> >>>
> >>>
> >>>Roelof Wobben schreef op 10-11-2014 13:47:
> >>>>Thanks all,
> >>>>
> >>>>I will try to make a fold solution as soon as I see that functional
> >>>>explained in the learnyouahaskell.
> >>>>
> >>>>Roelof
> >>>>
> >>>>
> >>>>Frerich Raabe schreef op 10-11-2014 11:43:
> >>>>>On 2014-11-10 11:16, Karl Voelker wrote:
> >>>>>>On Mon, Nov 10, 2014, at 01:50 AM, Roelof Wobben wrote:
> >>>>>>>What do you experts think of the different ways ?
> >>>>>>2 and 4 are quite similar, and both fine. 3 is not so good: guards
> >>>>>>provide weaker guarantees than patterns, and head and tail are partial
> >>>>>>functions.
> >>>>>In addition to what Karl wrote, I'd like to suggest not using the
> >>>>>semicolon all the time -- it's not needed and just adds noise.
> >>>>>
> >>>>>>All three implementations have in common that they do their own
> >>>>>>recursion. It would be a good exercise to try implementing last as a
> >>>>>>fold - in other words, letting the standard library do the recursion
> >>>>>>for
> >>>>>>you.
> >>>>>Right - I suggest trying to express the problem with the most abstract
> >>>>>function first, then consider using a fold, then use manual recursion.
> >>>>>in
> >>>>>your particular case you could exploit that for non-empty lists, getting
> >>>>>the last element of a list is the same as getting the first element of
> >>>>>a reversed list (and there are ready-made functions for reversing a list
> >>>>>and getting the first element of a list).
> >>>>>
> >>>>_______________________________________________
> >>>>Beginners mailing list
> >>>>Beginners at haskell.org
> >>>>http://www.haskell.org/mailman/listinfo/beginners
> >>>>
> >>>_______________________________________________
> >>>Beginners mailing list
> >>>Beginners at haskell.org
> >>>http://www.haskell.org/mailman/listinfo/beginners
> >>>
> >_______________________________________________
> >Beginners mailing list
> >Beginners at haskell.org
> >http://www.haskell.org/mailman/listinfo/beginners
> >
>