- Haskell-Cafe - Haskell.org

The IO monad is 45 years old
by oleg＠okmij.org 29 Dec '10

29 Dec '10

The unabated debate about exactly how much category theory one needs to know to understand that strange beast of IO prompts a thought if monads, like related continuations, are the things that are destined to be rediscovered time and time again. An old (1994) paper on category theory monads and functional programming included an interesting historical side-note. It turns out that the RealWorld-passing trick underlying the implementation of the IO monad, the trick that made it possible to embed truly side-effecting operations into pure Haskell -- the trick is 45 years old. It has been first published in February 1965. That 1965 paper also anticipated State and Writer monad, call/cc, streams and delayed evaluations, relation of streams with co-routines, and even stream fusion. First, here is the historical aside, cited from Jonathan M. D. Hill and Keith Clarke An Introduction to Category Theory, Category Theory Monads, and Their Relationship to Functional Programming. 1994 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.6497 [blockquote] 3 An historical aside Monads are typically equated with single-threadedness, and are therefore used as a technique for incorporating imperative features into a purely functional language. Category theory monads have little to do with single-threadedness; it is the sequencing imposed by composition that ensures single-threadedness. In a Wadler-ised monad this is a consequence of bundling the Kleisli star and flipped compose into the bind operator. There is nothing new in this connection. Peter Landin in his Algol 60 used functional composition to model semi-colon. Semi-colon can be thought of as a state transforming operator that threads the state of the machine throughout a program. The work of Peyton-Jones and Wadler has turned full circle back to Landin's earlier work as their use of Moggi's sequencing monad enables real side-effects to be incorporated into monad operations such as print. This is similar to Landin's implementation of his sharing machine where the assignandhold function can side-effect the store of the sharing machine because of the sequencing imposed by functional composition. Landin defined that `Imperatives are treated as null-list producing functions' [In Landin's paper, () is the syntactic representation of the empty list and not the unit.]. The assignandhold imperative is subtly different in that it enables Algol's compound statements to be handled. The function takes a store location and a value as its argument, and performs the assignment to the store of the sharing machine, returning the value assigned as a result of the function. Because Landin assumed applicative order reduction, the K combinator was used to return (), and the imperative was evaluated as a side effect by the unused argument of the K-combinator. Statements are formed by wrapping such an imperative in a lambda expression that takes () as an argument. Two consecutive Algol-60 assignments would be encoded in the lambda calculus as: Algol 60 | Lambda Calculus x:= 2; | ( (\() -> K () (assignandhold x 2)) . x:= -3; | (\() -> K () (assignandhold x (-3))) ) () By using a lambda with () as its parameter, () can be thought of as the `state of the world' that is threaded throughout a program by functional composition. [/blockquote] Peter Landin's paper is remarkable indeed: P. J. Landin. A correspondence between ALGOL 60 and Church's lambda notation. Communications of the ACM, 8(2):89-101, February 1965. (Part 2 in CACM Vol 8(2) 1965, pages 158-165.) http://portal.acm.org/citation.cfm?id=363749 First the reader will notice the `where' notation. Peter Landin even anticipated the debate on `let' vs `where', saying ``The only consideration in choosing between `let' and `where' will be the relative convenience of writing an auxiliary definition before or after the expression it qualifies.'' The ()-passing trick is described in full on p100, with remarkable clarity: ``Statements. Each statement is rendered as a 0-list- transformer, i.e. a none-adic function producing the nullist for its result. It achieves by side-effects a transformation of the current state of evaluation. ... Compound statements are considered as functional products (which we indicate informally by infixed dots).'' A remark ``However, input/output devices can be modeled as named lists, with special, rather restricted functions associated. ... Writing is modeled by a procedure that, operates on a list, and appends a new final segment derived from other variables. (Alternatively, a purely functional approach can be contrived by including the transformed list among the results.)'' anticipated the State and Writer monads as well. Another remark, in the section on Streams, ``This correspondence [laws of head/tail/cons] serves two related purposes. It enables us to perform operations on lists (such as generating them, mapping them, concatenating them) without using an `extensive,' item-by-item representation of the intermediately resulting lists; and it enables us to postpone the evaluation of the expressions specifying the items of a list until they arc actually needed. The second of these is what interests us here.'' and footnote 6, ``It appears that in stream-transformers we have a functional analogue of what Conway [12] calls "co-routines." show that Peter Landin understood streams, on-demand evaluation and even stream fusion.

2 1

ghc +RTS -M and -A behaving strange
by Johannes Waldmann 29 Dec '10

29 Dec '10

Hello. When I run a program compiled with ghc-6.12.3 like this: ... +RTS -A2G -M8G -s I get as an answer: Heap exhausted; Current maximum heap size is 0 bytes (0 MB); use `+RTS -M<size>' to increase it. and when I put the options ... +RTS -A2000M -M8000M -s I get Heap exhausted; Current maximum heap size is 4093640704 bytes (3904 MB); use `+RTS -M<size>' to increase it. and both numbers look strange. The behaviour of the program is also strange (instead of "heap exhausted" I'd expect it to do some smore garbage collections, which it does indeed without the -A option)

2 3

Re: [Haskell-cafe] Incrementially updating an array
by Henning Thielemann 29 Dec '10

29 Dec '10

On Wed, 29 Dec 2010, Robert Clausecker wrote: > Am Mittwoch, den 29.12.2010, 13:29 +0100 schrieb Henning Thielemann: >> >> I don't know, I hope it's doing its best. :-) You might compare speed of >> Array.accum with a manually written foldl with (//). > > At a glance onto it's sourcecode it actually does, but there are > actually other problems now, as my program now runs out of stack space. > (The list to accumulate contains about 1000000 elements). I guess it's > all about that the garbage collector can't handle such things very well. The pure number of 1000000 elements should not be a problem. You may post the failing code. I guess it has something to do with: http://www.haskell.org/haskellwiki/Stack_overflow

1 0

Re: [Haskell-cafe] [Haskell] haskell.org migration complete
by Henning Thielemann 29 Dec '10

29 Dec '10

Thomas Schilling schrieb: > I created http://www.haskell.org/haskellwiki/MigratingWikiContent to > list known issues and workarounds. Please feel free to extend that > page where needed. I liked to add that the Category link on each Wiki page is missing. How about an alternate CSS layout for the old Wiki style? Btw. unfortunately also in Konqueror CSS selections are not preserved across sessions. I did not like to add these items while having to log in over unsecure HTTP connection. Formerly I could just replace "http:" by "https:" which is no longer possible.

4 5

multi type addition
by william murphy 29 Dec '10

29 Dec '10

We were trying to make an addition function that, unlike the library one, could add numbers of different types from the typeclass 'Num.' We originally ran into a problem when trying to add (5 :: Integer) + 4.8, and were trying to define a new function that would be able to get that: (+') :: (Num a, Num b) => a -> b -> Float x +' b = d + e where d :: Float d = x e :: Float e = b This gave us the error: Couldn't match expected type `Float' against inferred type `b' `b' is a rigid type variable bound by the type signature for `pl' at test.hs:9:18 In the expression: b In the definition of `e': e = b In the definition of `pl': pl x b = d + e where d :: Float d = x e :: Float e = b Failed, modules loaded: none.

3 2

Having trouble with ftphs module
by aXqd 29 Dec '10

29 Dec '10

Hi all: I'm new to Haskell, and I ran into this problem recently while I am using ftphs module downloaded from hackage. Prelude> :m Network.FTP.Client Prelude Network.FTP.Client> h <- easyConnectFTP "xxx.xxx.xxx.xxx" *** Exception: FTP: "(unknown)" (line 2, column 1): unexpected "\r" expecting "\r\n" or Code 220 I am not the administrator of this FTP server. Hence all I've been told is that it is a "Microsoft FTP Server". I want to know 1. if this should be regarded as a bug of ftphs or not? 2. is there any other workaround other than the one below? Possible workaround: Implement another BAT script to do the FTP work and use system() to invoke it. Thanks in advance. -- Best regards, -Tian

1 0

Incrementially updating an array
by Robert Clausecker 28 Dec '10

28 Dec '10

Hi folks! I have the following problem. As code is most time easier to understand, let give an example what I try to do in C: unsigned int i,j; unsigned int r[100]; for (i = 0; i < 1000000; i++) { j = makeResult(); //j is known to be smaller than 100. r[j] = r[j] + 1; } (My C is poor, so please don't laugh) Currently I'm using a Data.Map for this, but as the result is bounded in this area, an array seems to be more appropreate. I don't want to mess with mutable arrays, but I can't find anything which does the same like Data.Map.insertWith for arrays in a reasonable way. In my example, the input comes from a lazy list and is than folded into the Map by insertWith (+) j 1 r. Is there any nice, quick way to do this with Arrays without using mutable ones? Yours, Robert Clausecker

3 2

Re: [Haskell-cafe] DFAs and self-referential data
by oleg＠okmij.org 28 Dec '10

28 Dec '10

Maxime Henrion wrote: > I've been playing with some code to work with DFAs, but I'm now faced > with an implementation problem. In order to have states that can > transition to themselves, it seems I would need self-referential data; > otherwise I would need to separate those transitions from the rest and > handle them specially in the code. Perhaps an old article http://okmij.org/ftp/misc.html#ccard-transform might be of some help. The article describes not only running a finite automaton (represented as a cyclic graph) on given input but also printing the automaton out and determinizing it: converting NFA to an equivalent DFA. The latter operation converts one cyclic graph to another.

2 1

How to "instance MonadIO Identity"?
by Magicloud Magiclouds 28 Dec '10

28 Dec '10

Hi, From another thread in this list, I got code as: > instance MonadIO Identity where > liftIO = id Well, it does not work for me as: Message.hs:22:12: Couldn't match expected type `Identity a' with actual type `IO a' Expected type: IO a -> Identity a Actual type: IO a -> IO a In the expression: id In an equation for `liftIO': liftIO = id -- 竹密岂妨流水过山高哪阻野云飞

3 5

instance for (Show ([(String, Int)] -> Int))
by Aaron Gray 27 Dec '10

27 Dec '10

How do I code an 'instance' declaration for '(Show ([(String, Int)] -> Int))'. I am new to instance declarations and am following the Happy examples :- http://www.haskell.org/happy/doc/html/sec-using.html#sec-other-datatypes The compiler is requesting an instance declaration for Show :- expr-eval.hs:334:23: No instance for (Show ([(String, Int)] -> Int)) arising from a use of `print' at expr-eval.hs:334:23-27 Possible fix: add an instance declaration for (Show ([(String, Int)] -> Int)) In the first argument of `(.)', namely `print' In the second argument of `(>>=)', namely `print . calc . lexer' In the expression: getContents >>= print . calc . lexer Many thanks in advance, Aaron

3 8