On Feb 3, 2009, at 10:15 AM, Dave Bayer wrote:
>
> The following takes forever, but it doesn't consume memory:
>
>> Prelude> :m Data.List
>> Prelude Data.List> genericIndex (zip (cycle [1..3]) (cycle [1..4]))
>> (1000^1000)
>
> So zip is doing something smart here with cyclic lists.

No, I just wasn't saving the head. This burns memory:

> Prelude Data.List> let a = zip (cycle [1..3]) (cycle [1..4])
> Prelude Data.List> head a
> (1,1)
> Prelude Data.List> genericIndex a (1000^1000)
> <interactive>: memory allocation failed (requested 2097152 bytes)
_______________________________________________
Beginners mailing list
[email]Beginners@haskell.org[/email]
[url]http://www.haskell.org/mailman/listinfo/beginners[/url]

I've been playing with parsing, for text filtering applications such as an alternate GHC literate preprocessor. Here, it pays to have one's monad handle both the input and output streams out of sight. Using ShowS-valued monads, one can express most grammatical constructs as simple composition. I'm sure many people have had this idea, but the resulting parsers that I write end up much shorter than any demo code I've seen. For example, the "code is indented, comments are flush, periods delimit block comments" literate preprocessor that I depend on daily (leaving out the heredoc code) is just

dot, comment, dotLine, commentLine, codeLine, dotBlock, delit ∷ Parser

dot = char '.'
comment = place "-- "

codeLine = white ∘ till (heredoc ∨ whiteLine) word
commentLine = comment ∘ line

dotLine = comment ∘ dot ∘ whiteLine
dotBlock = dotLine ∘ till (dotLine ∨ eof) (whiteLine ∨ commentLine)

delit = till (skip (many whiteLine) ∘ eof)
(whiteLine ∨ dotBlock ∨ codeLine ∨ commentLine)

However, I've struggled mightily to cleanly implement composition of function-valued monads. In the end I had to throw genericity under the bus to use the above notation. I'm asking for help, in case I'm missing something.

I cannot use Control.Category for a Monad, because of kind arity: Monad instances have one unbound *, while Category instances have two. Here are some toy experiments:

mcompose ∷ Monad m ⇒ m (b → c) → m (a → b) → m (a → c)
mcompose x y = do
f � x
g � y
return $ f . g

-- adapted from Control.Category

class Category cat where
unit ∷ cat a a
compose ∷ cat b c → cat a b → cat a c

instance Category (→) where
unit = id
compose = (.)

-- Monad wrapper

newtype Wrap m a b = Wrap { unwrap ∷ m (a → b) }

instance Monad m ⇒ Category (Wrap m) where
unit = Wrap $ return id
compose x y = Wrap $ mcompose (unwrap x) (unwrap y)

-- Other tries that fail

instance Monad m ⇒ Category (m (→)) where
unit = return id
compose = mcompose

-- Error:
-- The first argument of `Category' should have kind `* -> * -> *',
-- but `m (->)' has kind `*'
-- In the instance declaration for `Category (m (->))'

type MonadMap m a b = m (a → b)

instance Monad m ⇒ Category (MonadMap m) where
unit = return id
compose = mcompose

-- Error:
-- Type synonym `MonadMap' should have 3 arguments, but has been given 1
-- In the instance declaration for `Category (MonadMap m)'

I can see why each of these fail, but I also crave a language that allows ambiguity if exactly one interpretation compiles. For example, one could scrape the leaves of the tree (m (→)) to find the two *'s one wants, and one would think that my MonadMap type synonym would be a standard trick for exposing the two *'s without giving up on the other form. (I want to use the same type as both a monad and a category, as the goal here is very concise code with no gunk packing and unpacking crutch types for the compiler.)

So I threw "id" under the bus. Here are later experiments:

mcompose ∷ Monad m ⇒ m (b → c) → m (a → b) → m (a → c)
mcompose x y = do
f � x
g � y
return $ f . g

class Composable a b c | a b → c where
compose ∷ a → b → c

instance Composable (b → c) (a → b) (a → c) where
compose f g = f . g

instance Monad m ⇒ Composable (m (b → c)) (m (a → b)) (m (a → c)) where
compose = mcompose

unit ∷ Monad m ⇒ m (a → a)
unit = return id

tab ∷ Maybe ShowS
tab = Just (" " ++)

test1, test2 ∷ Monad m ⇒ m (a → a)
test1 = mcompose unit unit
test2 = compose unit unit

-- test2 error:
-- Could not deduce (Composable
-- (m (a -> a)) (m1 (a1 -> a1)) (m2 (a2 -> a2)))
-- from the context (Monad m2)
-- arising from a use of `compose' at Issue2.lhs:26:10-27

test3, test4 ∷ Maybe ShowS
test3 = mcompose tab tab
test4 = compose tab tab

It appears to me that type inference in type classes is broken. How else to explain why mcompose has no trouble figuring out that the monads are the same, but compose is stumped?

In the end, I threw genericity under the bus, and chose the parser type

type Parser = StateT String Maybe ShowS

so the second approach would work in practice.

I don't need to do this "my way" if there's an idiom (or -XAllowAliens compiler flag) that I need to learn. How does one do this sort of thing cleanly?

Thanks!

_______________________________________________
Beginners mailing list
[email]Beginners@haskell.org[/email]
[url]http://www.haskell.org/mailman/listinfo/beginners[/url]

Am Dienstag 02 Februar 2010 16:06:52 schrieb Dave Bayer:
> test1, test2 ∷ Monad m ⇒ m (a → a)
> Â* test1 = mcompose unit unit
> Â* test2 = compose Â*unit unit
>
> -- test2 error:
> -- Could not deduce (Composable
> -- (m (a -> a)) (m1 (a1 -> a1)) (m2 (a2 -> a2)))
> -- from the context (Monad m2)
> -- arising from a use of `compose' at Issue2.lhs:26:10-27
>
> Â* test3, test4 ∷ Maybe ShowS
> Â* test3 = mcompose tab tab
> Â* test4 = compose Â*tab tab
>
> It appears to me that type inference in type classes is broken. How else
> to explain why mcompose has no trouble Â*figuring out that the monads are
> the same, but compose is stumped?

Try removing the type signature for test2 and see what that gives:

Compose.hs:28:8:
No instance for (Composable (m (a -> a)) (m1 (a1 -> a1)) c)
arising from a use of `compose' at Compose.hs:28:8-25
Possible fix:
add an instance declaration for
(Composable (m (a -> a)) (m1 (a1 -> a1)) c)
In the expression: compose unit unit
In the definition of `test2': test2 = compose unit unit
Failed, modules loaded: none.

commenting out test2 and querying the type at the prompt:

*Compose> :t compose unit unit
compose unit unit
:: (Monad m,
Monad m1,
Composable (m (a -> a)) (m1 (a1 -> a1)) c) =>
c


In mcompose, you specified exactly which types to use, in particular that
there's only one monad involved.
In test2, the type checker must determine the types from scratch.

compose :: forall a b c. Composable a b c => a -> b -> c

test2 = compose unit unit

unit :: forall m a. Monad m => m (a -> a)

The type checker can't assume that both unit's in test2 have the same type,
so we have two monads (m, m1) and two types (a, a1) which are to be
composed to give a third type (c).

compose can only work when it knows the types of both arguments. It doesn't
know the type of unit (since that's polymorphic), so it can't work with
unit.

You can help it somewhat by adding more FunDeps to Composable,

class Composable a b c | a b → c, a c -> b, b c -> a where
compose ∷ a → b → c

, then it can work when it knows
a) the types of both arguments
or
b) the type of one argument and the type of the result.

Doesn't help with test2, though.
_______________________________________________
Beginners mailing list
[email]Beginners@haskell.org[/email]
[url]http://www.haskell.org/mailman/listinfo/beginners[/url]

Let me be as concise as I can, for a second try.

One can't make a function-valued monad into an instance of Category, because a Category takes two type arguments, while a Monad takes one?

I'm having serious cognitive dissonance here. The "back 40 acres" of the GHC manual is filled with brilliant work-arounds and references to research papers for far more arcane type dilemmas than this. My local hardware store is filled with pieces of copper that fit 1/2" pipe to 3/4" pipe, and they don't check for Ph.Ds at the door. But there's no provision in the language to fit a type class taking two arguments to a type class taking one argument?

I simply can't believe that I'm the first person to stumble over this. Either this is a famous rough edge, and others can list off a dozen similar circumstances where one gets stuck, or there's an easy work-around I'm just not seeing.

Can anyone confirm that it's simply not possible to plumb type classes the way I want to plumb them? If so, should I be proposing a language extension on a different mailing list?

On Feb 2, 2010, at 11:08 AM, Daniel Fischer wrote:

> You can help it somewhat by adding more FunDeps to Composable,
>
> class Composable a b c | a b → c, a c→ b, b c→ a where
> compose ∷ a → b → c

That's nice, I didn't think of that, but as you say it doesn't fix the problem.

_______________________________________________
Beginners mailing list
[email]Beginners@haskell.org[/email]
[url]http://www.haskell.org/mailman/listinfo/beginners[/url]

Dave Bayer wrote:
> Let me be as concise as I can, for a second try.
>
> One can't make a function-valued monad into an instance of Category,
> because a Category takes two type arguments, while a Monad takes one?
> [...]
> I simply can't believe that I'm the first person to stumble over
> this. Either this is a famous rough edge, and others can list off a
> dozen similar circumstances where one gets stuck, or there's an easy
> work-around I'm just not seeing.
>
> Can anyone confirm that it's simply not possible to plumb type
> classes the way I want to plumb them? If so, should I be proposing a
> language extension on a different mailing list?

You want a composition of functors

Wrap m ~ m ° (->)

but since higher-kinded polymorphism is a bit limited in Haskell
(decidability!), I don't think there's a way to make this an instance of
Category directly.


The usual solution is to make Wrap a newtype

newtype Wrap m a b = Wrap (m (a -> b))

instance Monad m => Category (Wrap m) where ...

and live with it.


If you want to be a bit more generic, you can use a newtype to denote
functor composition

{-# LANGUAGE TypeSynonymInstances #-}

newtype f `O` g a b = O (f (g a b))

instance Monad m => Category (m `O` (->)) where
id = return id
f . g = liftM2 (.) f g


But in both cases, there is no way around the fact that the Category
class needs a new type as argument.


Regards,
Heinrich Apfelmus

--
[url]http://apfelmus.nfshost.com[/url]

_______________________________________________
Beginners mailing list
[email]Beginners@haskell.org[/email]
[url]http://www.haskell.org/mailman/listinfo/beginners[/url]

Dave Bayer wrote:
> I've been playing with parsing, for text filtering applications such
> as an alternate GHC literate preprocessor. Here, it pays to have one's
> monad handle both the input and output streams out of sight. Using
> ShowS-valued monads, one can express most grammatical constructs as
> simple composition. I'm sure many people have had this idea, but the
> resulting parsers that I write end up much shorter than any demo code
> I've seen. For example, the "code is indented, comments are flush,
> periods delimit block comments" literate preprocessor that I depend on
> daily (leaving out the heredoc code) is just
>
> dot, comment, dotLine, commentLine, codeLine, dotBlock, delit ∷ Parser
>
> dot = char '.'
> comment = place "-- "
>
> codeLine = white ∘ till (heredoc ∨ whiteLine) word
> commentLine = comment ∘ line
>
> dotLine = comment ∘ dot ∘ whiteLine
> dotBlock = dotLine ∘ till (dotLine ∨ eof) (whiteLine ∨ commentLine)
>
> delit = till (skip (many whiteLine) ∘ eof)
> (whiteLine ∨ dotBlock ∨ codeLine ∨ commentLine)

This looks intriguing! Can you elaborate on how this works?


Regards,
Heinrich Apfelmus

--
[url]http://apfelmus.nfshost.com[/url]

_______________________________________________
Beginners mailing list
[email]Beginners@haskell.org[/email]
[url]http://www.haskell.org/mailman/listinfo/beginners[/url]

Thanks for all your answers.

Yes, Stephen explains exactly what I'm doing. I had been using a literate preprocessor that could have been written in Basic, but didn't include heredocs. It was very short, but I wanted something more idiomatic, so I stared at everyone's parser tutorials, wondering about monadic -vs- applicative etc. etc. The twin irritations of do notation everywhere, and ++ everywhere, pushed me over the edge to try ShowS-valued monads, and I loved how the code looked.

Normally I accept wrappers on everything as just how one does business in Haskell. As you say, to avoid undecidable type issues. Here I was struggling for days to make the code as lean as possible, and I could almost get away without wrappers.

I've been following the migration convention of ASCII for historic Prelude, Unicode for generic version of same, so I didn't want to steal ° for this one purpose; it should be categorical composition. I like the answer that m ° (->) is simply something different, I shouldn't think of it as composition. I had been using ◊ for this, I'll probably go back to it.

For a simple parser tutorial, or my immediate application of munging text e.g. literate preprocessor, ok to hardwire ShowS-valued monads. However, when one does have to break down and go into do notation (e.g. to implement my heredocs which steal the indentation from the closing EOF, and otherwise looks cleaner with multiple parsing passes), it might be slicker to use a general (a → b) type in place of ShowS. In fact, I believe one could do anything other parsers do, this way, with the benefit of most expressions being composition not requiring do-notation.

Anyhow, going further with monads returning (a → b) required me to make my peace with this composition issue, so I thank each of you!

I will write up a tutorial on this form of parsing when I submit my literate preprocessor to Cabal.

On Feb 4, 2010, at 6:25 AM, Stephen Tetley wrote:

> The parser has a type restricted return type - always a 'Hughes
> string' with efficient concatenation (ShowS :: String -> String)
> rather than some polymorphic answer (e.g a parse tree). For formatting
> it allows you to add text without consuming any:
>
> inserttext :: String -> Parser
> inserttext str = return (showString str)
>
> Or rewrite matched input:
>
> rewrite :: String -> String -> Parser
> rewrite inp out = string inp >> return (showString out)
>
> Or drop text, I presume this is what the place combinator does.
>
> Its a nice technique.
>
> On 4 February 2010 10:46, Heinrich Apfelmus <apfelmus@quantentunnel.de> wrote:
>>
>> This looks intriguing! Can you elaborate on how this works?
>

_______________________________________________
Beginners mailing list
[email]Beginners@haskell.org[/email]
[url]http://www.haskell.org/mailman/listinfo/beginners[/url]

Stephen Tetley wrote:
> The parser has a type restricted return type - always a 'Hughes
> string' with efficient concatenation (ShowS :: String -> String)
> rather than some polymorphic answer (e.g a parse tree). For formatting
> it allows you to add text without consuming any:
>
> inserttext :: String -> Parser
> inserttext str = return (showString str)
>
> Or rewrite matched input:
>
> rewrite :: String -> String -> Parser
> rewrite inp out = string inp >> return (showString out)
>
> Or drop text, I presume this is what the place combinator does.
>
> Its a nice technique.

Ah, nice; thanks for the explanation!


Regards,
Heinrich Apfelmus

--
[url]http://apfelmus.nfshost.com[/url]

_______________________________________________
Beginners mailing list
[email]Beginners@haskell.org[/email]
[url]http://www.haskell.org/mailman/listinfo/beginners[/url]

Thanks for all your answers.

Yes, Stephen explains exactly what I'm doing. I had been using a literate preprocessor that could have been written in Basic, but didn't include heredocs. It was very short, but I wanted something more idiomatic, so I stared at everyone's parser tutorials, wondering about monadic -vs- applicative etc. etc. The twin irritations of do notation everywhere, and ++ everywhere, pushed me over the edge to try ShowS-valued monads, and I loved how the code looked.

Normally I accept wrappers on everything as just how one does business in Haskell. As you say, to avoid undecidable type issues. Here I was struggling for days to make the code as lean as possible, and I could almost get away without wrappers.

I've been following the migration convention of ASCII for historic Prelude, Unicode for generic version of same, so I didn't want to steal ° for this one purpose; it should be categorical composition. I like the answer that m ° (->) is simply something different, I shouldn't think of it as composition. I had been using ◊ for this, I'll probably go back to it.

For a simple parser tutorial, or my immediate application of munging text e.g. literate preprocessor, ok to hardwire ShowS-valued monads. However, when one does have to break down and go into do notation (e.g. to implement my heredocs which steal the indentation from the closing EOF, and otherwise looks cleaner with multiple parsing passes), it might be slicker to use a general (a → b) type in place of ShowS. In fact, I believe one could do anything other parsers do, this way, with the benefit of most expressions being composition not requiring do-notation.

Anyhow, going further with monads returning (a → b) required me to make my peace with this composition issue, so I thank each of you!

I will write up a tutorial on this form of parsing when I submit my literate preprocessor to Cabal.

On Feb 4, 2010, at 6:25 AM, Stephen Tetley wrote:

> The parser has a type restricted return type - always a 'Hughes
> string' with efficient concatenation (ShowS :: String -> String)
> rather than some polymorphic answer (e.g a parse tree). For formatting
> it allows you to add text without consuming any:
>
> inserttext :: String -> Parser
> inserttext str = return (showString str)
>
> Or rewrite matched input:
>
> rewrite :: String -> String -> Parser
> rewrite inp out = string inp >> return (showString out)
>
> Or drop text, I presume this is what the place combinator does.
>
> Its a nice technique.
>
> On 4 February 2010 10:46, Heinrich Apfelmus <apfelmus@quantentunnel.de> wrote:
>>
>> This looks intriguing! Can you elaborate on how this works?
>

_______________________________________________
Beginners mailing list
[email]Beginners@haskell.org[/email]
[url]http://www.haskell.org/mailman/listinfo/beginners[/url]