Talk:Haskell/Understanding arrows

From Wikibooks, the open-content textbooks collection

Jump to: navigation, search

Contents

[edit] Ross Paterson

Ross Paterson has kindly given us permission to use material from the Haskell arrows page, as well as the parts of the GHC User's guide on arrows. But be careful! His Arrows and computation book chapter belongs to his publisher, so we'd better not use that. -- Kowey 11:40, 15 February 2006 (UTC)

[edit] Shae Erisson

In #haskell, Shae Erisson has helpfully given us permission to use material from the TMRWiki introduction to arrows. Thanks again, shapr! -- Kowey 14:50, 20 February 2006 (UTC)

[edit] /Kowey

I am currently using the sub talk page /Kowey to learn about arrows and eventually dump the results on the module. Feel free to modify it, of course -- Kowey 13:12, 15 February 2006 (UTC)

[edit] The plan

Here's what I had in mind for the arrows module: while optimising monadic parser combinator libraries is very interesting in itself, it is probably too hard to think about in the very beginning, when all the reader really wants to do is understand the arrow machinery.

  1. We start with a very brief description of what arrows are for
  2. Then dive straight into the machinery, with diagrams (done)
  3. Show a simple implementation of arrows
  4. Show some simple stream processor stuff (note: i don't understand this yet)
  5. Explain the the S+W parser, using the arrow machinery directly! Don't bother with <+> - this is where shapr's tutorial comes in
  6. Discuss the relationship between monads and arrows.

-- Kowey 11:25, 22 February 2006 (UTC)

May I suggest introducing the syntactic sugar first, and then showing how it maps to the underlying Arrow functions? This follows the style for explaining monads: start with the sugared version and then show how the ">>=" and ">>" functions support it. I spent a long time trying to understand this business with pairs. Then I got on to the syntactic sugar and it started to make sense.

Its not made easier by the various papers that put everything into point-free form. Very clever, but much harder to follow because there are no meaningful variable names to act as signposts.

PaulJohnson 22:02, 1 July 2006 (UTC)

Hmm, I do think the sugar should be introduced at some point. Right now though, the way we explain monads starts with the bind operator and only mentions the sugar as the side note in the end. That being said, the reason I did that is to insist on the underlying mechanisms (binding) because usually by the time my target audience reads the tutorial, it has already used monads some and just want to know how it works. With arrows, it's a bit different because said audience has likely NOT used them before, so maybe introducing the sugar first would work. (I don't actually know what the sugar does yet). In any case, we'll have to play around with this. I still haven't got all the way up to understanding the arrowfied S+W parser and that is my principle blocker. -- Kowey 18:20, 6 July 2006 (UTC)

[edit] Sigh...

I should really highlight the fact that I still don't know what I'm talking about re: arrows. The module is really just what I have gleaned from arrow literature and mostly me trying to understand what's going on. So if you feel like I'm going down some pedagogical dead-end, and that the module needs to take a different tack, please be bold about it and change everything around. The point being, the structure of this text is NOT really on purpose and subject to being turned upside down. -- Kowey 16:54, 9 July 2006 (UTC)

Alright... I really do think I'm writing myself into a dead-end here. What I want to do is partly what Paul suggested
  • Have two arrow chapters, Haskell/Arrows and Haskell/Understanding arrows. The present chapter will become Understanding arrows
  • In the first chapter, do NOT explain arrows. Show the sugar notation, and walk the user through some exercises... the only problem is that I need a simple task that we can do with arrows (even if it's not necessarily made for arrows). It will be like Paul said. First the reader learns how to work with arrows without really really getting why they work, and then we show what's behind the curtain. So any ideas for simple exercises? -- Kowey 09:41, 10 July 2006 (UTC)

[edit] metaphor obsolete

I should point out that thanks to Apfelmus's intervention, the monad chapter no longer relies on the metaphor. So we should rewrite the intro to reflect this (I think here it's kinda handy, but no need to make an allusion) -- Kowey (talk) 16:49, 16 March 2008 (UTC)

[edit] Parser nitpicking - (>>>) is buggy

About the definition of (>>>) for arrow parsers: if charA's dynamic component doesn't check whether the first character of input is correct, relying on that having been done by the static component, then, in case of charA 'a' >>> charA 'b', who's going to invoke the static component of the second character parser? The definition of (>>>) shown in the section certainly doesn't do it, which results in charA 'a' >>> charA 'b' accepting 'a' followed by any character.

Either the contract for a parser should require that its dynamic component rejects all invalid input (i.e. is a validating parser), or (>>>) should invoke the static component of its right operand. --Alexey Feldgendler (talk) 15:53, 15 March 2009 (UTC)

You're probably right. In any case, the exact details are in the D&P paper.
-- apfeλmus 09:16, 16 March 2009 (UTC)
If I'm right, then the code in this article needs to be fixed. :-) --X-Man (talk) 19:22, 19 March 2009 (UTC)
Certainly. :-) I'd like to make sure, though. I'm not familiar with the details myself, could you have a look at the Swierstra and Duponchel's paper for a correct implementation?
-- apfeλmus 07:47, 21 March 2009 (UTC)
Looked at the paper [1] (BTW, shouldn't it be referenced from the article?) and found the same problem in D&P's definition of dpseq. In their notation, dpsymbol 'a' `dpseq` dpsymbol 'b' will accept 'a' followed by any character. I'm confused now. It's probably something obvious that I'm overlooking, but to me it looks like the paper contains the same glaring bug. --X-Man (talk) 04:53, 22 March 2009 (UTC)
I've had a look at the paper but it doesn't mention arrows at all, does it? IIRC, there was a successor paper that does, though. Could you dig it up and have a look?
In any case, the irony is that the parser combinators presented in the paper you mentioned are an instance of Haskell/Applicative Functors.
-- apfeλmus 20:53, 23 March 2009 (UTC)
Using arrows for parsers was John Hughes' idea. Duponcheel writes in his blog: One of John Hughes motivations for introducing the Arrow model in Haskell was a class of error correcting parsers (developed by Doaitse Swierstra and Luc Duponcheel) that could be modelled using Arrows, but not using Monads (cfr. afp-arrows). However, if there was a mistake in the original parser paper that didn't mention arrows, it could just as well have been carried over to later papers. To me it seems like the parsers in [2] have a bug, even though they aren't expressed as arrows. What do you think about it? /me is in terrible need of one more sensible person to confirm I'm not delusional. --X-Man (talk) 10:49, 28 March 2009 (UTC)
I've had a closer look now. The main definition dpseq for sequencing the dynamic parsers is on page 11 and it indeed does not check for errors. This can be used to produce a bug as you showed. In fact, invokeDet (dpsymbol 'a') alone will never fail which would be a bug already. However, the choice combinator dpalt does check for errors.
But note that the goal of the paper is to include automatic error correction and accepting any input would be the right behavior in this case. So, the important and different question is whether there is a bug in the final version of the parsers on page 16.
In other words, the point is that the definition of the dynamic parsers in the paper is quite different from the one in the wikibook. Even the version from page 11 includes an extra Follow s argument which the wikibook version doesn't have. So, the two aren't really comparable.
But what to do for the wikibook? (See below)
-- apfeλmus 09:36, 2 April 2009 (UTC)
What to do?
The full D&P stuff is probably too complicated to be included here. Also, parsers are best viewed as applicative functors anyway. But describing one of the main motivation for arrows would be nice, so a dumbed-down version similar to the present one would be great to have. So, it would be best if someone could turn it into something that actually works.
-- apfeλmus 09:36, 2 April 2009 (UTC)

[edit] "Arrow Limitations"

While most of this article is excellent and very helpful, the section titled "Arrows aren't the answer to every question" is not very useful. While I'm sure arrows have limitations, this paragraph provides no insight into what these limitations might be. There are only nebulous mentions of research done on IRC channels and pointers to references that don't exist. While it might be useful to have a section on the limitations of arrows, I propose that for the time being this small section (and the list of names below) be removed as they add no value and seem somewhat unprofessional. I would make this change myself but I don't want to step on anybody's toes. Walkie (talk) 09:07, 8 April 2009 (UTC)

I'm fine with it, go ahead.
-- apfeλmus
Done, thanks. Walkie (talk) 08:29, 10 April 2009 (UTC)

[edit] "Not compiled in ghc-6.10.3"

possible fix bellow.

   import Prelude hiding (id, (.))
   import Control.Arrow
   import Data.List
   import Control.Category
   data Parser s a b = P (StaticParser s) (DynamicParser s a b)
   data StaticParser s = SP Bool [s]
   newtype DynamicParser s a b = DP ((a,[s]) -> (b,[s]))
   spCharA :: Char -> StaticParser Char
   spCharA c = SP False [c]
   dpCharA :: Char -> DynamicParser Char Char Char
   dpCharA c = DP (\(_,x:xs) -> (c,xs))
   charA :: Char -> Parser Char Char Char
   charA c = P (SP False [c]) (DP (\(_,x:xs) -> (c,xs)))
   instance Eq s => Category (Parser s) where
       id = P (SP True []) (DP (\(a,[s]) -> (a,[s])))
       (P (SP empty1 start1) (DP p1)) . (P (SP empty2 start2) (DP p2)) =
           (P (SP (empty1 && empty2) (if not empty1 then start1 else start1 `union` start2)) (DP (p1 . p2)))
   instance Eq s => Arrow (Parser s) where
       arr f = P (SP True []) (DP (\(b,s) -> (f b,s)))
       first (P sp (DP p)) = (P sp (DP (\((b, d),s) -> let (c, s') = p (b,s) in ((c,d),s'))))

--VladimirSorokin (talk) 12:34, 3 July 2009 (UTC)

Retrieved from "http://en.wikibooks.org/wiki/Talk:Haskell/Understanding_arrows"