Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Exotic List Monads

hackage.haskell.org

Post reply on HN
Print view View original

11–20 of 27 posts

Re: Exotic List Monads

#11

Post by uryga »

nemo1618 wrote: post #8

> The usual list monad is only one of infinitely many ways to turn the List functor into a monad. So simple, and yet this is a point that I think is rarely made clear enough in "monad explainers." For instance, they almost always talk about "the Maybe monad" -- but this is conflating two things: the Maybe data type , and the Monad instance defined on that type. Propagating "Nothing" is not inherent to the Maybe data…

> Propagating "Nothing" is not inherent to the Maybe data type, it's just a convenient behavior to have.

nitpick about this particular example: is there another lawful implementation of Monad for Maybe? i can't think of any, apart from the trivial

  pure _  = Nothing
  _ >>= _ = Nothing
(eyeballing the lawfulness, but it'll all be `Nothing` so all the equalities should hold, trivially :D)

Re: Exotic List Monads

#12

Post by lmm »

> In each case return is singleton (it is not known if there exists a monad on lists with a different return).

The "diagonal" monad join [[a, b, c, ...], [1, 2, 3, ...], [x, y, z, ...], ...] = [a, 2, z, ...] has return a = [a, a, a, ...], though I guess it's hard to define it in a way that's well-behaved for finite lists, so you might not consider it "a monad on lists".

Re: Exotic List Monads

#13

Post by gizmo686 »

nemo1618 wrote: post #8

> The usual list monad is only one of infinitely many ways to turn the List functor into a monad. So simple, and yet this is a point that I think is rarely made clear enough in "monad explainers." For instance, they almost always talk about "the Maybe monad" -- but this is conflating two things: the Maybe data type , and the Monad instance defined on that type. Propagating "Nothing" is not inherent to the Maybe data…

At the language level, FP seperates data from behavior. However, in practice, even functional programmers still tend to couple data and behavior.

For instance, not much would change about programming in Haskell if List was defined as an abstract type, so users couldn't see its constructor or interact with it in any way except through its functions.

In OOP languages, this is unambiguous because the function/interface implementation is explicitly defined as part of the type. In FP languages, this is a little less clear because the implementation can be defined anywhere (although, should really be either near the data declaration, or the typeclass declaration).

Re: Exotic List Monads

#14

Post by mjhoy »

uryga wrote: post #11
nemo1618 wrote: post #8

> The usual list monad is only one of infinitely many ways to turn the List functor into a monad. So simple, and yet this is a point that I think is rarely made clear enough in "monad explainers." For instance, they almost always talk about "the Maybe monad" -- but this is conflating two things: the Maybe data type , and the Monad instance defined on that type. Propagating "Nothing" is not inherent to the Maybe data…

> Propagating "Nothing" is not inherent to the Maybe data type, it's just a convenient behavior to have. nitpick about this particular example: is there another lawful implementation of Monad for Maybe? i can't think of any, apart from the trivial pure _ = Nothing _ >>= _ = Nothing (eyeballing the lawfulness, but it'll all be `Nothing` so all the equalities should hold, trivially :D)

I don't think that holds for left identity:

    pure a >>= f ≡ f a

Re: Exotic List Monads

#15

Post by tel »

uryga wrote: post #11
nemo1618 wrote: post #8

> The usual list monad is only one of infinitely many ways to turn the List functor into a monad. So simple, and yet this is a point that I think is rarely made clear enough in "monad explainers." For instance, they almost always talk about "the Maybe monad" -- but this is conflating two things: the Maybe data type , and the Monad instance defined on that type. Propagating "Nothing" is not inherent to the Maybe data…

> Propagating "Nothing" is not inherent to the Maybe data type, it's just a convenient behavior to have. nitpick about this particular example: is there another lawful implementation of Monad for Maybe? i can't think of any, apart from the trivial pure _ = Nothing _ >>= _ = Nothing (eyeballing the lawfulness, but it'll all be `Nothing` so all the equalities should hold, trivially :D)

The trivial implementation isn't law abiding. This law doesn't hold (written in Kleisli form for simplicity)

    pure >=> f == f  (left identity)
There are no other monads for Maybe. First, any definition of pure must be Just as Nothing doesn't work because of left identity and parametricity prevents any other funny business. Now, by law we know

    pure a >>= f == f a
Thus, we must define

    Just a >>= f = f a
So the only variable is what (Nothing >>= f) does. For (f: A -> B) we must end up with a Maybe B. We don't have one to start and we can produce Maybe values only via Nothing and Just. So, either >>= is the standard definition or we have to do

    Nothing >>= f = Just (_: B)     -- we can achieve a B only via use of f, so
    Nothing >>= f = Just (f (_: A)) -- now we are stuck, there are no values of A
Thus, we must define

    pure a = Just a
    
    Just a >>= f  = f a
    Nothing >>= f = Nothing

Re: Exotic List Monads

#16

Post by klodolph »

mjhoy wrote: post #14
uryga wrote: post #11

Earlier quoted context omitted.

> Propagating "Nothing" is not inherent to the Maybe data type, it's just a convenient behavior to have. nitpick about this particular example: is there another lawful implementation of Monad for Maybe? i can't think of any, apart from the trivial pure _ = Nothing _ >>= _ = Nothing (eyeballing the lawfulness, but it'll all be `Nothing` so all the equalities should hold, trivially :D)

I don't think that holds for left identity: pure a >>= f ≡ f a

Exactly, and the right identity is also violated:

    m >>= pure ≡ m

Re: Exotic List Monads

#17

Post by [deleted] »

mjhoy wrote: post #14
uryga wrote: post #11

Earlier quoted context omitted.

> Propagating "Nothing" is not inherent to the Maybe data type, it's just a convenient behavior to have. nitpick about this particular example: is there another lawful implementation of Monad for Maybe? i can't think of any, apart from the trivial pure _ = Nothing _ >>= _ = Nothing (eyeballing the lawfulness, but it'll all be `Nothing` so all the equalities should hold, trivially :D)

I don't think that holds for left identity: pure a >>= f ≡ f a

[deleted]

Re: Exotic List Monads

#18

Post by odyssey7 »

nemo1618 wrote: post #8

> The usual list monad is only one of infinitely many ways to turn the List functor into a monad. So simple, and yet this is a point that I think is rarely made clear enough in "monad explainers." For instance, they almost always talk about "the Maybe monad" -- but this is conflating two things: the Maybe data type , and the Monad instance defined on that type. Propagating "Nothing" is not inherent to the Maybe data…

As someone who recently learned monads, this exactly was a point of confusion for me.

Re: Exotic List Monads

#19

Post by 082349872349872 »

lmm wrote: post #12

> In each case return is singleton (it is not known if there exists a monad on lists with a different return). The "diagonal" monad join [[a, b, c, ...], [1, 2, 3, ...], [x, y, z, ...], ...] = [a, 2, z, ...] has return a = [a, a, a, ...], though I guess it's hard to define it in a way that's well-behaved for finite lists, so you might not consider it "a monad on lists".

for finite lists, why not just have it return in k-diagonal order? (sort of like Hope's "diagonal comprehension" but with wraparound repetition)

Re: Exotic List Monads

#20

Post by 082349872349872 »

zgotsch wrote: post #5

I don’t see how this has broad appeal, but at least the Mazewalk interpretation is cute.

Mazewalk is more than cute, it also occurs when encoding trees whose leaves are operations and whose branches are relative context modifications. (where our key optimisation is that we needn't restore contexts in tail position, just as Mazewalk doesn't palindromise its last unary tree)

Consider it as an alternative to the more common strategy of absolutising the modifications onto the leaves in a first tree walk, and then executing all the now-labelled leaves in arbitrary order in a second pass.

Post reply on HN