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

Dontdie YCH dontdieych at gmail.com
Mon Nov 10 17:05:52 UTC 2014 

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.
2014. 11. 11. 오전 1:19에 "Stefan Höck" <efasckenoth at gmail.com>님이 작성:

> > 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
> > >
> >
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20141111/474b5221/attachment.html>

More information about the Beginners mailing list