Matthew, I would strongly suggest taking a look on SPJ's presentation at OSCON 2007 (video at http://blip.tv/file/324976). He shows a very interesting circular list (with a zipper). Since you are interested in functional data structures, Chris Okasaki's book "Purely Functional Data Structures" is a great source too! On Tue, Feb 3, 2009 at 00:53, Erik de Castro Lopo

wrote:

Matthew J. Williams wrote:

...

How would one mimic, in Haskell, a C++ circular linked list i.e., where the last element precedes (points to) the first?

Try this, "Tying the Knot":

http://www.haskell.org/haskellwiki/Tying_the_Knot

Erik -- -- ----------------------------------------------------------------- Erik de Castro Lopo ----------------------------------------------------------------- "I consider C++ the most significant technical hazard to the survival of your project and do so without apologies." -- Alistair Cockburn _______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

-- Rafael Gustavo da Cunha Pereira Pinto Electronic Engineer, MSc.

cycle doesn't actually construct in memory a cyclic data structure, as one might in C. It's more like those repeat bars in sheet music.

It doesn't? cycle xs = xs' where xs' = xs ++ xs' That sure looks like a cyclic data structure to me! xs' references a thunk which computes (xs ++ xs'); this thunk, in turn, references xs'. cycle is memory-efficient precisely because it *does* actually construct a cyclic data structure. -Brent

So the "repeat bars" are there until the first pass through the list completes, otherwise cycle would be bottom on infinite lists. Thereafter, you're saying that a core dump would reveal a completely homogeneous memory representation, just like C code, that one could pass through the foreign function interface to C code? GHC seems to have a special awareness of cyclic lists. For example, ghci computes

(zip (cycle [1..3]) (cycle [1..4])) !! (1000^1000)

immediately, as if it knows enough to compute 1000^1000 mod 12, by repeated squaring. On Feb 3, 2009, at 9:17 AM, Brent Yorgey wrote:

It doesn't?

cycle xs = xs' where xs' = xs ++ xs'

That sure looks like a cyclic data structure to me! xs' references a thunk which computes (xs ++ xs'); this thunk, in turn, references xs'. cycle is memory-efficient precisely because it *does* actually construct a cyclic data structure.

On Feb 3, 2009, at 10:04 AM, Daniel Fischer wrote:

...

GHC seems to have a special awareness of cyclic lists. For example, ghci computes

...

(zip (cycle [1..3]) (cycle [1..4])) !! (1000^1000)

No, it's that the type of (!!) is [a] -> Int -> a, and 1000^1000 :: Int is 0.

...

immediately, as if it knows enough to compute 1000^1000 mod 12, by repeated squaring.

Thanks. 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.

On Tue, Feb 03, 2009 at 09:54:46AM -0500, Dave Bayer wrote:

So the "repeat bars" are there until the first pass through the list completes, otherwise cycle would be bottom on infinite lists. Thereafter, you're saying that a core dump would reveal a completely homogeneous memory representation, just like C code, that one could pass through the foreign function interface to C code?

I'm not really sure what you mean by "repeat bars". There really is a cyclic data structure in memory at all times--it's just that until the first pass through the list, part of it is a thunk. After a complete pass to the list, however, a core dump would indeed reveal something like what you suggest.

GHC seems to have a special awareness of cyclic lists. For example, ghci computes

...

(zip (cycle [1..3]) (cycle [1..4])) !! (1000^1000)

immediately, as if it knows enough to compute 1000^1000 mod 12, by repeated squaring.

I came to the same conclusion as Daniel but it took me a few minutes of puzzlement. Besides, it should actually be equal to (2,1), not (1,1). =) -Brent

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.

Hi Dave You might need more that a type system extension for this one. I've called your composition operator (*>>*), if you stack the type signatures together I can't see a way of getting from (*>>*) to (.). Compare it to the Kleisli composition of monads - where the step to (.) is more apparent (swap '-> m' for cat): -- (.) :: cat b c -> cat a b -> cat a c -- (.) :: b `cat` c -> a `cat` b -> a `cat` c -- infix -- (*>>*) :: Monad m => m (b -> c) -> m (a -> b) -> m (a -> c) -- Kleisli composition does satisfy Category -- _Kleisli_ :: Monad m => (b -> m c) -> (a -> m b) -> (a -> m c) I think I've derived what you are doing below with Graham Hutton's parser monad, the 'easy work around' is to use (*>>*) rather than try to use (.): module Fun where -- Starting with a Graham Hutton's parser as it is (probably) the -- simplest monadic parser newtype Parser a = Parser { parse :: (String -> [(a,String)]) } instance Monad Parser where return a = Parser (\cs -> [(a,cs)]) p >>= f = Parser (\cs -> concat [parse (f a) cs' | (a,cs') <- parse p cs]) item :: Parser Char item = Parser (\cs -> case cs of "" -> [] (c:cs) -> [(c,cs)]) zero :: Parser a zero = Parser (\cs -> []) sat :: (Char -> Bool) -> Parser Char sat p = do {c <- item; if p c then return c else zero} char0 :: Char -> Parser Char char0 c = sat (c==) char :: Char -> Parser ShowS char c = do {ch <- sat (c==) ; return (showChar c) } -- consume but don't produce ? place0 :: String -> Parser String place0 str = do { str' <- mapM char0 str; return "" } place :: String -> Parser ShowS place str = place0 str >> return (\s -> s) -- no string aka id string0 :: String -> Parser String string0 str = mapM char0 str string :: String -> Parser ShowS string str = do { str' <- string0 str; return (showString str) } -------------------------------------------------------------------------------- dot :: Parser ShowS dot = char '.' comment :: Parser ShowS comment = place "-- " runParser :: Parser ShowS -> String -> String runParser p inp = post $ ((parse p) inp) where post [(ans,_)] = ans $ "" post xs = error (unlines $ map (\(f,cs) -> show (f "",cs)) xs) demo1 :: String demo1 = runParser (comment >> dot) "-- ." startPragma :: Parser ShowS startPragma = string "{-#" demo2 :: String demo2 = runParser (startPragma) "{-#" space :: Parser ShowS space = char ' ' languageU :: Parser ShowS languageU = string "LANGUAGE" -- first attempt - 'endo' style keeps the same type (*>*) :: Monad m => m (a -> a) -> m (a -> a) -> m (a -> a) mf *>* mg = do { f <- mf; g <- mg; return (f.g) } demo3 :: String demo3 = runParser (startPragma *>* space *>* languageU) "{-# LANGUAGE" -- second attempt - 'bluebird' style - proper composition -- (more general) (*>>*) :: Monad m => m (b -> c) -> m (a -> b) -> m (a -> c) mf *>>* mg = do { f <- mf; g <- mg; return (f.g) } demo4 :: String demo4 = runParser (startPragma *>>* space *>>* languageU) "{-# LANGUAGE" -- (.) :: cat b c -> cat a b -> cat a c -- (*>>*) :: Monad m => m (b -> c) -> m (a -> b) -> m (a -> c) -- ??? -- Kleisli composition does satisfy Category -- _Kleisli_ :: Monad m => (b -> m c) -> (a -> m b) -> (a -> m c) -- TYPE ERROR -- demo5x :: String -- demo5x = runParser (startPragma . space . languageU) "{-# LANGUAGE"

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 -- http://apfelmus.nfshost.com

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 wrote:

...

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

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 -- http://apfelmus.nfshost.com