Need better explanation of the 'flipThree' example in LYAH

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

Need better explanation of the 'flipThree' example in LYAH

Olumide
Dear List,

I'm trying to understand the following example from LYAH

     import Data.List (all)

     flipThree :: Prob Bool
     flipThree = do
         a <- coin
         b <- coin
         c <- loadedCoin
         return (all (==Tails) [a,b,c])

Where
     import Data.Ratio
     newtype Prob a = Prob { getProb :: [(a,Rational)] } deriving Show

and

     data Coin = Heads | Tails deriving (Show, Eq)

     coin :: Prob Coin
     coin = Prob [(Heads,1%2),(Tails,1%2)]

     loadedCoin :: Prob Coin
     loadedCoin = Prob [(Heads,1%10),(Tails,9%10)]

The result:

     ghci> getProb flipThree
     [(False,1 % 40),(False,9 % 40),(False,1 % 40),(False,9 % 40),
      (False,1 % 40),(False,9 % 40),(False,1 % 40),(True,9 % 40)]

See http://learnyouahaskell.com/for-a-few-monads-more#making-monads.

My understanding of what's going on here is sketchy at best. One of
several explanations that I am considering is that all combination of a,
b and c are evaluated in (==Tails) [a,b,c] but I cannot explain how the
all function creates 'fuses' the list [f a, f b, f c]. I know that all f
xs = and . map f xs (the definition on hackage is a lot more
complicated) but, again, I cannot explain how the and function 'fuses'
the list [f a, f b, f c].

If I'm on the right track I realize that I'm going to have to study the
list the between list comprehensions and the do-notation in order how
all the return function create one Prob.

Regards,

- Olumide

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

Re: Need better explanation of the 'flipThree' example in LYAH

Francesco Ariis
Hello Olumide,

On Tue, Aug 21, 2018 at 01:04:01AM +0100, Olumide wrote:
> My understanding of what's going on here is sketchy at best. One of several
> explanations that I am considering is that all combination of a, b and c are
> evaluated in (==Tails) [a,b,c] but I cannot explain how the all function
> creates 'fuses' the list [f a, f b, f c]. I know that all f xs = and . map f
> xs (the definition on hackage is a lot more complicated) but, again, I
> cannot explain how the and function 'fuses' the list [f a, f b, f c].

Let's copy the relevant monad instance:

    instance Monad Prob where
        return x = Prob [(x,1%1)]
        m >>= f = flatten (fmap f m)

and desugar `flipThree:

    flipThree = coin       >>= \a ->
                coin       >>= \b ->
                loadedCoin >>= \c ->
                return (all (==Tails) [a,b,c])


Now it should be clearer: `coin >>= \a -> ...something...` takes `coin`
(Prob [(Heads,1%2),(Tails,1%2)]), applies a function (\a -> ...) to all
of its elements, flattens (probability wise) the result.
So approximately we have:

    1. some list ([a, b])
    2. nested lists after applying `\a -> ...` [[a1, a2], [b1, b2]]
    3. some more flattened list [a1, a2, b1, b2]

`\a -> ...` itself contains `\b ->` which cointains `\c ->`, those are
nested rounds of the same (>>=) trick we saw above.
At each time the intermediate result is bound to a variable (\a, \b
and \c), so for each triplet we can use `all`.

> If I'm on the right track I realize that I'm going to have to study the list
> the between list comprehensions and the do-notation in order how all the
> return function create one Prob.

Indeed I recall working the example on paper the first time I read it:
once you do it, it should stick!
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Need better explanation of the 'flipThree' example in LYAH

Olumide
Hi Francesco,

Thanks as always for your reply. (I note that you've replied many of my
questions.)

I have not replied because I've been thinking very hard about this
problem and in particular about the way the do notation is desugared in
this case and something doesn't sit right with me. (Obviously there's
something I've failed to understand.)

Take for example

do
     a <- coin
     b <- coin
     return ([a,b])

This would desugar into

do a <- coin
     do b <- coin
         return [a,b]

and ultimately into

coin >>= ( \a ->
coin >>= ( \b ->
return [a,b] ))

Noting that m >>= f = flatten (fmap f m) , and recursively applying
expanding >>= I get

flatten( fmap (\a -> coin >>= ( \b -> return [a,b] ) ) coin )

and

flatten( fmap (\a -> ( flatten( fmap ( \b -> return [a,b] ) coin ) ) coin )

Is this how to proceed and how am I to simplify this expression?

Regards,

- Olumide




On 21/08/18 02:00, Francesco Ariis wrote:

> Hello Olumide,
>
> On Tue, Aug 21, 2018 at 01:04:01AM +0100, Olumide wrote:
>> My understanding of what's going on here is sketchy at best. One of several
>> explanations that I am considering is that all combination of a, b and c are
>> evaluated in (==Tails) [a,b,c] but I cannot explain how the all function
>> creates 'fuses' the list [f a, f b, f c]. I know that all f xs = and . map f
>> xs (the definition on hackage is a lot more complicated) but, again, I
>> cannot explain how the and function 'fuses' the list [f a, f b, f c].
>
> Let's copy the relevant monad instance:
>
>      instance Monad Prob where
>          return x = Prob [(x,1%1)]
>          m >>= f = flatten (fmap f m)
>
> and desugar `flipThree:
>
>      flipThree = coin       >>= \a ->
>                  coin       >>= \b ->
>                  loadedCoin >>= \c ->
>                  return (all (==Tails) [a,b,c])
>
>
> Now it should be clearer: `coin >>= \a -> ...something...` takes `coin`
> (Prob [(Heads,1%2),(Tails,1%2)]), applies a function (\a -> ...) to all
> of its elements, flattens (probability wise) the result.
> So approximately we have:
>
>      1. some list ([a, b])
>      2. nested lists after applying `\a -> ...` [[a1, a2], [b1, b2]]
>      3. some more flattened list [a1, a2, b1, b2]
>
> `\a -> ...` itself contains `\b ->` which cointains `\c ->`, those are
> nested rounds of the same (>>=) trick we saw above.
> At each time the intermediate result is bound to a variable (\a, \b
> and \c), so for each triplet we can use `all`.
>
>> If I'm on the right track I realize that I'm going to have to study the list
>> the between list comprehensions and the do-notation in order how all the
>> return function create one Prob.
>
> Indeed I recall working the example on paper the first time I read it:
> once you do it, it should stick!
> _______________________________________________
> 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: Need better explanation of the 'flipThree' example in LYAH

Francesco Ariis
In reply to this post by Francesco Ariis
Hello Olumide,

On Mon, Sep 17, 2018 at 12:15:58AM +0100, Sola Aina wrote:
> flatten( fmap (\a -> ( flatten( fmap ( \b -> return [a,b] ) coin ) ) coin )
>
> Is this how to proceed and how am I to simplify this expression?

I get a slightly different final expression:

    flatten (fmap (\a -> flatten (fmap (\b -> return [a,b]) coin)) coin)
    -- notice the lack of `(` before the second `flatten`

This could be rewritten as:

    flatMap (\a -> flatMap (\b -> return [a,b]) coin) coin

    -- flatMap :: (a1 -> Prob a2) -> Prob a1 -> Prob a2
    -- flatMap f x = flatten (fmap f x)

which is a bit easier on the eyes. This expression cannot be simplified
any further if we don't bring to the table the definition of `coin`!
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Need better explanation of the 'flipThree' example in LYAH

Olumide
Thanks Francesco. You are right. I had one too many rbraces.

However from the definition

fmap f (Prob xs) = Prob $ map (\(x,p) -> (f x , p))  xs

and  x = Head | Tails suggests to me that f ought to be a function like
any (==Heads) that applies to [x]

Therefore I've changed the desugared expression to

flatten( fmap (\a -> flatten( fmap ( \b -> return ( any (== Heads) [a,b]
) ) coin ) ) coin )

So that from the definition of coin, the inner expression

fmap ( \b -> return ( any (== Heads) [a,b] ) ) coin

expands to

fmap ( \b -> return ( any (== Heads) [a,b] ) ) Prob[ (Heads, 1%2) ,
(Tails, 1%2) ]

Detour: writing all this made me realize that (1) the lambda is applied
the lambda to all elements(?) of the Prob, and (2) the term a represents
each element of the outer Prob.

So that the above expression becomes

Prob $ [ (any (==Heads)[a,Head], 1%2) , (any (==Head)[a,Tails], 1%2) ]

writing all this made me realize that (1) the lambda is applied to all
elements(?) of the Prob, and that (2) the term a represents each element
of the outer Prob -- I think I am starting to see the
similarity/connection between the do-notation and list comprehensions.

Returning to the above expression, when the term a is Heads, we get

Prob [ (return any (==Heads)[Heads,Head], 1%2) , (return any
(==Head)[Heads,Tails], 1%2) ]

and because

return any (==Heads)[Heads,Head]  = Prob[True,1%1] , and
return any (==Heads)[Heads,Tails] = Prob[True,1%1]

The above expression becomes

Prob [ (Prob[True,1%1] , 1%2 ) , ( Prob[True,1%1] , 1%2 ) ]

The double Prob makes it clear why flatten is needed.

I'll stop here and wait for your feedback.

BTW, I'm considering using GHC.Proof to assert that this sequence of
reductions is equivalent.

Regards,

- Oumide


On 17/09/18 01:09, Francesco Ariis wrote:

> Hello Olumide,
>
> On Mon, Sep 17, 2018 at 12:15:58AM +0100, Sola Aina wrote:
>> flatten( fmap (\a -> ( flatten( fmap ( \b -> return [a,b] ) coin ) ) coin )
>>
>> Is this how to proceed and how am I to simplify this expression?
>
> I get a slightly different final expression:
>
>      flatten (fmap (\a -> flatten (fmap (\b -> return [a,b]) coin)) coin)
>      -- notice the lack of `(` before the second `flatten`
>
> This could be rewritten as:
>
>      flatMap (\a -> flatMap (\b -> return [a,b]) coin) coin
>
>      -- flatMap :: (a1 -> Prob a2) -> Prob a1 -> Prob a2
>      -- flatMap f x = flatten (fmap f x)
>
> which is a bit easier on the eyes. This expression cannot be simplified
> any further if we don't bring to the table the definition of `coin`!
> _______________________________________________
> 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