discovered this handy snippet today (duh :):
foldl (<|>) Nothing [Nothing, Just 1, Nothing, Just 2] Just 1
basically, pick first Just from a list of Maybes http://hackage.haskell.org/package/base-4.9.0.0/docs/Control-Applicative.htm...
If you want something even simpler: asum [Nothing, Just True, Nothing, Just False]
From Data.Foldable :)
On Wed, 28 Dec 2016, 10:56 am Imants Cekusins,
discovered this handy snippet today (duh :):
foldl (<|>) Nothing [Nothing, Just 1, Nothing, Just 2] Just 1
basically, pick first Just from a list of Maybes
http://hackage.haskell.org/package/base-4.9.0.0/docs/Control-Applicative.htm... _______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Imants Cekusins wrote:
foldl (<|>) Nothing [Nothing, Just 1, Nothing, Just 2] Just 1
Apart from Ollie's suggestion of asum, here are a few more interesting points that come up from your observation: In your solution, you would want to use foldr, not foldl. The left fold forces reading the entire list to the end even though you already hit your Just. A right fold will short circuit. That also means the right fold will even work with an infinite list, as long as there is at least one Just somewhere in the list. (Note that asum uses foldr under the hood. :)) And if you still do use a left fold, you'll want foldl' (from Data.List) rather than foldl. The foldl from the Prelude will build up a pile of unevaluated lazy thunks the size of your list, and only then evaluate all the <|> calculations all at once. So this will crash with a stack overflow error if your list is very large. Whereas foldl' will perform all of the <|> calculations one by one in constant memory. Yitz
you would want to use foldr, not foldl
foldl vs foldr baffles me a bit. in Erlang http://erlang.org/doc/man/lists.html#foldl-3 use of *foldl* is suggested. I got used to this and usually use foldl. another reason is: it appears that in Haskell - same as Erlang - *foldl* enumerates items in "natural" order: in [1,2] 1 is passed to the fn, then 2 *foldr* on the other hand begins with 2 and ends with 1. however: *foldr* arg order: a -> acc is more natural. I very rarely deal with large lists and never (so far) with inifinites. for this case for which I consider and use Alternatives - the list would be 2 - 5 items long. The order though is important.
asum [Just 1, Just 2] Just 1 asum [Nothing, Just 1, Nothing, Just 2, Nothing] Just 1
looks "naturally" ordered: tested left to right. I may not understand the workings (memory and such) of foldl vs foldr however I hope that for small lists it is sufficient to focus on the order of element processing. order matters. This example hopefully confirms that foldr begins @ end, foldl begins @ start. Same as in Erlang ;) Prelude Data.Foldable> *foldr* (\i1 acc1 -> i1 + acc1 * 2) 0 [1,2] 5 Prelude Data.Foldable> *foldl* (\acc1 i1 -> i1 + acc1 * 2) 0 [1,2] 4
foldr doesn't begin anywhere. https://vimeo.com/64673035 On 29/12/16 06:43, Imants Cekusins wrote:
you would want to use foldr, not foldl
foldl vs foldr baffles me a bit.
in Erlang http://erlang.org/doc/man/lists.html#foldl-3 use of *foldl* is suggested. I got used to this and usually use foldl.
another reason is: it appears that in Haskell - same as Erlang - *foldl* enumerates items in "natural" order: in [1,2] 1 is passed to the fn, then 2
*foldr* on the other hand begins with 2 and ends with 1.
however: *foldr* arg order: a -> acc is more natural.
I very rarely deal with large lists and never (so far) with inifinites.
for this case for which I consider and use Alternatives - the list would be 2 - 5 items long. The order though is important.
asum [Just 1, Just 2] Just 1 asum [Nothing, Just 1, Nothing, Just 2, Nothing] Just 1
looks "naturally" ordered: tested left to right.
I may not understand the workings (memory and such) of foldl vs foldr however I hope that for small lists it is sufficient to focus on the order of element processing.
order matters. This example hopefully confirms that foldr begins @ end, foldl begins @ start. Same as in Erlang ;)
Prelude Data.Foldable> *foldr* (\i1 acc1 -> i1 + acc1 * 2) 0 [1,2] 5 Prelude Data.Foldable> *foldl* (\acc1 i1 -> i1 + acc1 * 2) 0 [1,2] 4
_______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
I wrote:
you would want to use foldr, not foldl
Imants Cekusins wrote:
foldl enumerates items in "natural" order: in [1,2] 1 is passed to the fn, then 2 foldr on the other hand begins with 2 and ends with 1.
The list is not reversed by either one of them. And in both of them, the first element of the list is examined first. With foldl, you apply the complete operation to each element of the list in turn, all the way to the end of the list. With foldr, you start with the first element and say: Let's think about what will happen when we apply the operation to the first element with the result of the entire fold from the second element onward. Knowing only the first element at this time, can we already say what the result will be? In this case, there are two possibilities: If the first element is Just, then yes, we already know the result, and we can discard the rest of the fold without ever actually computing it. If the first element is Nothing, then we don't know the result yet. But we do know that the first element is irrelevant, so we discard it and move on. Doesn't foldr seem like a more natural way to do what you want here? The reason this doesn't work in Erlang is because Erlang is a strict language. When we try to apply the operation with first parameter the first element of the list and second parameter the rest of the fold, Erlang does the entire calculation of that second parameter - the entire fold - before it even starts thinking about the operation. Regards, Yitz
thank you Tony and Yitzchak. I may understand it one day ;) it is important to understand it alright. I remember spending half a day over unexpected (for me) results of recursive functions that contained folds. In the end I settled for TChan - a queue with predictable behaviour (my view of it - not necessarily correct). Yitzchak, how about this: Prelude Control.Applicative> *foldl* (<|>) Nothing [Just 1, Nothing, Just 2, Nothing] Just 1 Prelude Control.Applicative> *foldr* (<|>) Nothing [Just 1, Nothing, Just 2, Nothing] Just 1 ? I guess this is due to the nature of (<|>), no? Anyway, I'd use asum instead of fold_ for Alternatives. for non-Alternative cases, Erlang analogy seems to be a useful rule of thumb for foldl & foldr over shorter lists . After all, what matters most is what results to expect. *foldl* and *foldr* may yield different results for the same list & similar processing fn (save for different arg order).
Imants Cekusins wrote:
Yitzchak, how about this:
Prelude Control.Applicative> foldl (<|>) Nothing [Just 1, Nothing, Just 2, Nothing] Just 1 Prelude Control.Applicative> foldr (<|>) Nothing [Just 1, Nothing, Just 2, Nothing] Just 1
? I guess this is due to the nature of (<|>), no?
Yes, you are right. <|> for Maybe satisfies the associative law: (x <|> y) <|> z == x <|> (y <|> z) for all x, y, and z. So it does not matter if you apply it from right to left or from left to right.
Anyway, I'd use asum instead of fold_ for Alternatives.
Agreed. For the actual problem, Ollie is right. I just thought you might be interested in these other concepts that come up from your good thinking. Regards, Yitz
participants (4)
-
Imants Cekusins -
Oliver Charles -
Tony Morris -
Yitzchak Gale