Alternative

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
11 messages Options
Reply | Threaded
Open this post in threaded view
|

Alternative

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.html#g:2

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Alternative

Oliver Charles-3

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, <[hidden email]> wrote:
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.html#g:2
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Alternative

Imants Cekusins
 something even simpler:

cheers Oliver. asum is better.

how is it possible to (<|>) results in:


type Am m  = (Alternative m, Monad m)

(Am m, Am n) => (a -> m (n b)) -> [a] -> m (n b)

?

say, m (n b) is 
IO (Maybe b)

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Alternative

Imants Cekusins
how is it possible to (<|>) results in:

 .. sequence + asum did it:

do
            lm2 <- sequence m1
            asum lm2 `shouldBe` (Just 1)
            where m1 = [pure Nothing, pure (Just 1), pure (Just 2), pure Nothing]::[IO (Maybe Int)]

thank you Oliver. good tip.

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Alternative

Yitzchak Gale
In reply to this post by Imants Cekusins
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
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Alternative

Imants Cekusins
> you would want to use foldr, not foldl

foldl vs foldr baffles me a bit.

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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Alternative

Tony Morris-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.

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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

signature.asc (499 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Alternative

Yitzchak Gale
In reply to this post by Imants Cekusins
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
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Alternative

Imants Cekusins
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).

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Alternative

Yitzchak Gale
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
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Alternative

Imants Cekusins
Yitzchak, I am interested alright. However for very practical purpose.

> (x <|> y) <|> z == x <|> (y <|> z)

understood. thank you Yitzchak.

we will revisit recurse & fold problem I ran into earlier. probably in Jan though.


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners