List layouts

[nsch]

Hi!

I want to propose a new GHC extension called ListLayouts?. It's basically a do-notation for pure lists and was initially meant to offer an alternative to the current do-notation monad "exploits" as seen in libraries like e.g. blaze-html, but it is of course a lot more general.

What it'd look like in practice shows this little example:

{-# LANGUAGE ListLayouts #-}

import Data.Monoid

main :: IO ()
main = mapM_ putStrLn $++
  "These are list layouts."
  "Let me know what you think. :)"

allFalse :: All
allFalse = mconcat $++
  All True
  let f = All True
      t = All False
  t
  f

This simply translates to (a : let b = c in (d : ... )) etc. I already started working on this extension and the above example already works:

» nils@n-sch.de. ../inplace/bin/ghc-stage2 LISTLAYOUT-TEST.hs --interactive
GHCi, version 7.5.20111229: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
[1 of 1] Compiling Main             ( LISTLAYOUT-TEST.hs, interpreted )
Ok, modules loaded: Main.
*Main> allFalse
All {getAll = False}
*Main> :main
These are list layouts.
Let me know what you think. :)
*Main>

ListLayouts? currently support two statements, regular expressions (i.e. list elements) and let bindings. It could be thought to add the .. notation thing and maybe even comprehension notations, e.g.:

ex = $++
  1
  2..5
  x  | x <- [6..], x <= 10
  11 | False

This should result in the list [1,2,3,4,5,6,7,8,9,10]. Adding these features to the current existing code should be pretty much straight forward.

In my opinion this extension would fit in nicely, as it is kind of the counterpart to monad comprehensions (which practically add list notation to monads). It shouldn't be necessary to make it any more general (e.g. use monoids, semigroups or any other, potentially new, type class instead of lists) since almost every list-like datatype has it's own fromList function (Data.Map.fromList, Data.Set.fromList, Data.Monoid.mconcat etc.) and using functions instead of class instances is a lot more convenient in most cases, too.

So please let me know what you think about this idea and whether or not you would be willing to add this extension to GHC. I would, of course, be willing to do all the coding.

[ehird]

Copying what I said  on reddit for the record:

I don't like $++; it should be a textual keyword, like do.

I would be in favour of this, but I think it should be generalised to any Monoid; things like the various serialisation libraries want to be monoids, but use monads just to get do notation.

[nsch]

Replying to ehird:

I don't like $++; it should be a textual keyword, like do.

There have been a couple of good suggestions in those reddit comments. My favorites so far:

• cat or mcat (if we use monoids instead of plain lists)
• be (as in not do-ing anything)

On IRC there has also been mentioned that further layouts could be thought of, e.g. an "application" layout which simply applies all its elements to the previous function:

foo $$
  bar a b
  baz x y

=>

foo (bar a b) (baz x y)

Or a record layout:

MyRecord {{
  a = 0
  b = c

=>

MyRecord { a = 0, b = c }

If you're willing to accept these (and maybe more in the future) layouts I'd guess the extension should be named "ExtendedLayouts" or something similar.

[simonpj]

I'm afraid I don't understand this feature. Could you write a Wiki page that gives the specification? A single example isn't enough to say

• what the syntax is
• when it typechecks
• how it desugars

Maybe I'm wrong, but it has the smell of being closely related to the work of George and friends on monad comprehensions; see MonadComprehensions. In paricular their as-yet-unimplemented proposal to overload list literals; Section 5.2 of their paper [ Bringing back monad comprehensions] at the 2011 Haskell Symposium. I'm adding George and Jeroen in cc.

[simonmar]

As I said on IRC, the proposal feels a bit narrow to warrant a whole extension. It's only saving one character per line, after all. Perhaps generalising to Monoids makes it worthwhile though.

[giorgidze]

I am in favour of overloading the existing list notation. In addition to the section in our paper that Simon is referring to there is a lengthy GHC mailing list discussion linked below.

My original post:  http://www.mail-archive.com/glasgow-haskell-users@haskell.org/msg20447.html

My summary incorporating feedback from several GHC users and developers:  http://www.mail-archive.com/glasgow-haskell-users@haskell.org/msg20518.html

The reason I like the list notation overloading proposal is that it subsumes (modulo extra character in the syntax) the ListLayout? proposal and two existing GHC extensions (string literal overloading and the DPH array notation).

I was extremely busy last few months and did not have time to implement and experiment with the list notation overloading. I would like to come back to it in near future, but I am not sure on exact timing as yet.

Nils, maybe we can combine forces on this.

Cheers, George

[simonmar]

George, I don't think overloading list notation subsumes the ListLayout proposal. Unless I'm misunderstanding, the whole point of ListLayout is to avoid typing those extra characters. The users who want ListLayout don't care about overloading - they want essentially do-notation to build lists.

I'm not saying that overloading list notation is a bad thing, just that I don't think it addresses the issue raised here. (I'm not convinced that the issue raised here is worth addressing, though).

[nsch]

Replying to simonpj:

I'm afraid I don't understand this feature. Could you write a Wiki page that gives the specification?

I have added the ExtendedLayouts page. Please tell me if anything is unclear or not understandable.

Maybe I'm wrong, but it has the smell of being closely related to the work of George and friends on monad comprehensions; see MonadComprehensions. In paricular their as-yet-unimplemented proposal to overload list literals; Section 5.2 of their paper [ Bringing back monad comprehensions] at the 2011 Haskell Symposium. I'm adding George and Jeroen in cc.

It would be pretty much the exact opposit of said proposal. It would make it possible to write lists (as a monoid) without the actual list notation [ , ]. I hope the wiki page makes that clear.

Btw, I'm the guy who did most of the monad comprehension coding, so I'm well familiar with that extension. :)

[ehird]

Here's some justifications of this feature from my point of view (talking about the version generalised to monoids, as I think it's the best option):

There are quite a few widely-used libraries that use a monad for what is essentially an optimised Writer w () over a specific w. Examples:

*  blaze-html uses a  laws-breaking Monad instance so it can  use layout

*  cereal has an  optimised Writer monad for serialisation; the user doesn't care about the PutM monad itself, just the type Put = PutM () alias

So, one thing this is useful for is output and specification of complex nested structures. These monads are exclusively used in a monoidal style (indeed, if they're only used with the () result type (as e.g. blaze-html must be) they're equivalent to monoids), have no use for do-notation binds, and would be far more comfortable with a notation specifically designed for monoids.

You could just use mconcat [...] everywhere, but writing long lists over multiple lines is ugly. A nice thing about a monoid notation is that a lot of the libraries can be seen (and can be implemented as) imperatively streaming their output to a handle, so an imperative sequencing notation and operations like put :: Word8 -> M are reasonable. In light of this, and because the other proposed names seem too likely to clash to me, my favourite name so far is mdo, for "monoidal do". The only worry there is that it would clash with the obsolete recursive do notation, but it *is* deprecated, and its history of being a reserved keyword will mean that clashes are unlikely.

[ehird]

Forgot to add:

As far as desugaring goes, I would suggest that it reorder the expressions (including flattening nested mdos) to be right-associative, and to avoid mappending things with mempty, e.g.

mdo { }                      ≡ mempty
mdo { a }                    ≡ a
mdo { mdo { as... }; bs... } ≡ mdo { as...; bs... }
mdo { a; as... }             ≡ a `mappend` mdo { as... }

[nsch]

Replying to ehird:

As far as desugaring goes, I would suggest that it reorder the expressions (including flattening nested mdos) to be right-associative, and to avoid mappending things with mempty, e.g.

Actually, this extension would never ever (!) use mempty, which is why some have argued that Monoid may not exactly be the correct type class for this. A Semigroup typeclass might be more appropriate:

class Semigroup a where
  gappend :: a -> a -> a

Which should satisfy associativity:

(a `gappend` b) `gappend` c = a `gappend` (b `gappend` c) 

The Semigroup instance for monoids is trivial.

mdo { } ≡ mempty

I think this should return a "Empty 'mdo' block" error, just as do does. Simply for consistency and to avoid that 'mdo' (or 'be' or whatever keyword will be used) will be used as synonym for mempty. Again, the use of semigroups would offer an obvious solution to this question.

mdo { a } ≡ a

This is obvious.

mdo { mdo { as... }; bs... } ≡ mdo { as...; bs... }

This would translate to:

=>  mdo { as ... } `mappend` bs `mappend` ...
=>  (as `mappend` ..) `mappend` bs `mappend` ...

Because of associativity this is equivalent to what you suggested.

mdo { a; as... } ≡ a mappend mdo { as... }

Again, this is the obvious translation rule.

And by the way, mdo is already a reserved key word.

[ehird]

Replying to nsch:

Replying to ehird:

As far as desugaring goes, I would suggest that it reorder the expressions (including flattening nested mdos) to be right-associative, and to avoid mappending things with mempty, e.g.

Actually, this extension would never ever (!) use mempty, which is why some have argued that Monoid may not exactly be the correct type class for this. A Semigroup typeclass might be more appropriate: {{{ class Semigroup a where gappend :: a -> a -> a }}} Which should satisfy associativity: {{{ (a gappend b) gappend c = a gappend (b gappend c) }}} The Semigroup instance for monoids is trivial.

Fair enough; I'd stick with Monoid because it's already in base; ideally  semigroups would move in.

This would translate to: {{{ => mdo { as ... } mappend bs mappend ... => (as mappend ..) mappend bs mappend ... }}} Because of associativity this is equivalent to what you suggested.

My special case was intentional; while the two expressions must have equivalent *results*, right-associative use of mappend is more efficient for basically all Monoids. This is why, e.g. RWH suggests using a difference-list rather than [] as the monoid of a Writer.

And by the way, mdo is already a reserved key word.

As I said:

The only worry there is that it would clash with the obsolete recursive do notation, but it *is* deprecated, and its history of being a reserved keyword will mean that clashes are unlikely.

The new notation for recursive do-notation is do rec.

[simonmar]

Replying to ehird:

My special case was intentional; while the two expressions must have equivalent *results*, right-associative use of mappend is more efficient for basically all Monoids. This is why, e.g. RWH suggests using a difference-list rather than [] as the monoid of a Writer.

Then it should be a RULE, not part of desugaring. Otherwise you get strange effects like a difference in performance between

mdo { mdo {..}, x }

and

let z = mdo {..} in mdo {z, x}

and I'm not sure I'm comfortable with a built-in bias in the associativity of mappend - it might be true that most existing Monoids are naturally right-associative, but that's not necessarily the case in general.

[nsch]

Does the performance between

mconcat [a,b,..]

and

a `mappend` (b `mappend` ..)

actually differ much in performance (at all?) if mconcat is foldr mappend mempty? GHC should (is? out of the box? with use of some pragmas?) be able to get the same performance out of both versions, shouldn't it? I'm not familiar enough with the whole optimization process/benchmarking GHC to tell for sure…

The big problem I have with using monoids/semigroups for this layout is that it seems to be such a specialization already of general (yes, general) lists. After all, the reason why I like the be keyword so much is that lists literally don't do anything but concatenating one statement to the other. Monoids already do a lot more (combining all values). And then there's this question about left/right associativity, where I totally agree with simonmar - this shouldn't be a "built-in bias". Using lists for the be layout would offer a simple solution to this: define your own specialized version of mconcat and apply it to the be-list before using your monoid. After all, the mconcat function already generalizes all lists to monoids if the monoid instance of the list elements is given! Furthermore, my initial list-example doesn't work anymore with a monoid/semigroup layout as mappend for lists is (++) and not (:) (which wouldn't match the a -> a -> a type of mappend) and you would get something like

    Couldn't match expected type `[Bool]' with actual type `Bool'
    In the expression: True
    In a stmt of a semigroup layout block: True
    In the expression:
      be { True;
           False }

if the resulting type should be a simple list (here: of boolean values) instead of a custom monoid that would do exactly the same.

[NeilMitchell]

Note that you can already use do to define a Monoid:

data Wrap m a = Wrap m a

unwrap :: Wrap m a -> m
unwrap (Wrap m a) = m

wrap :: m -> Wrap m ()
wrap m = Wrap m ()

instance Monoid m => Monad (Wrap m) where
    return = Wrap mempty
    Wrap m1 a1 >>= f = Wrap (m1 `mappend` m2) a2
       where Wrap m2 a2 = f a1

foo :: [Int]
foo = unwrap $ do
    wrap [1,2,3]
    wrap [4,5]
    wrap [6]

If you sugar up a particular monad and add some nicer types and helper functions, it can end up looking quite pleasant. I use this trick in the Shake library, so rules can be specified using either do notation or as a monoid, even though they are really a monoid.

(Personally, I agree with Simon Marlow, that it's probably not a problem that needs solving - but hopefully the above insight might solve some of the issues)

[nsch]

Replying to NeilMitchell:

Note that you can already use do to define a Monoid:

Hi Neil,

In  your own talk about your Shake library, people are asking you (with good reason) why you're using a monadic structure in your library and you respond with "it has great syntax and it looks like a Make file" and that "shake is just a list, it isn't a monad in any remote way" (minute 24+ in the video). This is exactly why I suggested a new keyword for a new non-monadic layout which represents a simple list instead of wrapping everything (here: a monoid) into something that looks like something completly different (a monad). "do" and my proposed "be" (or your Monoid-wrap) do not behave the same way at all!

When I worked with the implementation of monad comprehensions we (me and my team) chose a very simple way to make your monad comprehension dependend on different type classes, depending on what statements your were using in your comprehension. For example would you need a MonadZip instance if your comprehension was using parallel statements, or a MonadGroup instance if it was using a group statement – but if it didn't a simple Monad instance for binding/returning values would be completely sufficient. This was possible because the different statements were compatible to each other, i.e. adding a parallel statement didn't change the behaviour of the previous statements.

This is not the same with the "monoid-do" notation! My first attempt at this proposal was a do that did basically what I have done with monad comprehensions: Require a Monoid instance if we only had regular expression statements (i.e. the (>>) case) and require a Monad instance as soon as we used a binding statement (the (>>=) case):

{-# LANGUAGE MonoidDo #-}

newtype MyMonoid = MyMonoid Int

instance Monoid MyMonoid where
  mempty = MyMonoid 0
  mappend (MyMonoid x) (MyMonoid y) = MyMonoid (x+y)
  mconcat = foldr mappend mempty

myMonoid :: MyMonoid
myMonoid = do
  MyMonoid 1
  MyMonoid 2
  -- this works as expected for a monoid and results in "3"

newtype MyMonoidMonad a = MyMonoidMonad a

instance Monad MyMonoidMonad where
  return x                               = MyMonoidMonad x
  (MyMonoidMonad _) >> (MyMonoidMonad y) = MyMonoidMonad y
  (MyMonoidMonad x) >>= f                = f x

instance Monoid a => Monoid (MyMonoidMonad a) where
  mempty = MyMonoidMonad mempty
  mappend (MyMonoidMonad x) (MyMonoidMonad y) = MyMonoidMonad (x `mappend` y)
  mconcat = foldr (\(MyMonoidMonad x) (MyMonoidMonad y) -> MyMonoidMonad (x `mappend` y)) mempty

-- For this data type a monoid-do notation would produce a different result than
-- the monadic do-notation does!

myMonoidMonad :: MyMonoidMonad MyMonoid
myMonoidMonad = do
  MyMonoidMonad (MyMonoid 1)
  MyMonoidMonad (MyMonoid 2)
  -- monoid result: 3
  -- monad  result: 2 !!

This example shows clearly: do should not be used for monoids as the behaviour of (>>) and mappend is totally different! Yes, it is possible to write those hacks (this is the reason why I came up with this proposal), but it is not obvious to the user that you're not actually doing something monadic in your library that way. Using be {..} would be a lot cleaner (and more convenient too), both for the developers and the end user.

[giorgidze]

Thanks Simon and Nils for your clarifications.

I agree with Nils that the use of the do notation for non-monadic structures should not be encouraged.

As for notations for constructing lists, I like the current standard notation with square brackets, commas, and dots (for arithmetic sequences). The standard notation works very well for single line as well as for multiline indented and nested definitions.

I do not see a compelling reason as to why Haskell needs an alternative notation for constructing lists.

Cheers, George

[nsch]

Replying to giorgidze:

I do not see a compelling reason as to why Haskell needs an alternative notation for constructing lists.

Hi George,

The compelling reason is that it already exists and is being used, only under a false and incorrect name. This extension would simply legitimate the use of layout for stuff that is not a monad, I don't even see a reason why monads should be so special with their 'do'. This is nothing overwhelmingly new or creative but just a simple reaction to something that people in the Haskell community seem to miss.

[igloo]

I think there are still some open design questions here that would be better worked out on a wiki page, so I'm going to close this ticket for now.