May 2007 - Haskell-Cafe

reversing big list with constant heap space used
by Sergey Perminov 18 May '07

18 May '07

How to solve task of reversing big list with constant heap space used? Amount of heap space used grows exponentially in following examples: 1: main = putStrLn.show.head $reverse [1..10000000] 2 (GHC): import Data.List main = putStrLn.show.head $foldl' (flip (:)) [] [1..10000000] 3 (GHC): import Control.Monad main = foldM (\x y -> return $ y:x) [] [1..10000000] >>= putStrLn.show.head -- Best regards, Sergey Perminov

6 6

Tail Recursion within the IO Monad
by Rob Hoelz 18 May '07

18 May '07

Hello everyone, You may have seen my message about how I'm writing a binding to a C library. This is another question related to that. So, let's say I have a linked list implemented in C. Here's what its definition looks like: struct __linked_list { void *data; struct __linked_list *next; }; typedef struct __linked_list linked_list_t; void *linked_list_getdata(linked_list_t *); linked_list_t *linked_list_next(linked_list_t *); Keep in mind, this is just a segment. So using the Haskell FFI, I import these into my .hsc file: data LinkedList = LL (Ptr linked_list_t) foreign import ccall unsafe "linked_list.h" linked_list_getdata :: Ptr LinkedList -> IO Ptr a foreign import ccall unsafe "linked_list.h" linked_list_next :: Ptr LinkedList -> IO Ptr LinkedList So now that that's done, I attempt to write a Ptr LinkedList -> [String] function (assuming the given LinkedList is holding c strings): linkedListToStringList :: Ptr LinkedList -> IO [String] linkedListToStringList listPtr = if listPtr == nullPtr then return [] else do item <- linked_list_getdata listPtr next <- linked_list_next listPtr cStr <- peek item hStr <- peekCString cStr t <- linkedListToStringList next return (hStr : t) This is just ugly...making the recursive call first, THEN consing the value on? However, this is the only way I could think of doing it. I figure there are three possibilities from here: 1) Leave this code alone, as GHC will optimize it because it's smart. 2) There's a way to more effectively write this code! Change it! 3) Roll my own optimization. I know how to do 3, but I'd rather avoid it. I guess I'm looking for an answer to 2, but if 1 is true, that'd be ok too. Could anyone give me a hand? And as long as I'm asking, is there some kind of monadic function composition operator? I'd like to clean up the above with something like peekCString . peek . linked_list_getdata... Many thanks, Rob Hoelz

5 6

Safe/Unsafe calls with the GHC Foreign Function Interface
by Rob Hoelz 18 May '07

18 May '07

More questions from Rob regarding his mysterious bindings... So I've been reading the docs for the FFI, and it's my understanding that foreign functions imported as "unsafe" are faster, but they've got a problem with callbacks. From what I read, I believe that I should just make a foreign function safe if it sets up a callback; is this correct? Normally I wouldn't bother people with questions like this, but I'd rather be absolutely certain and avoid tracking down a strange bug later. Many thanks as always, Rob

2 2

haskell-lang.org
by Dipen Javia 18 May '07

18 May '07

Hello, I just registered haskell-lang.org a week ago for 1 year. I was wondering if anybody wants it, I am selling it for regular price i got it which is $8 from godaddy. If you have an account with godaddy, tranferring is easy and free. If you dont have an account you can get one for free. Thanks. -- Dipen Javia

1 0

Re: global variables
by Big Chris 18 May '07

18 May '07

On Thu, 17 May 2007, Jason Dagit wrote: > Well, it seems to me that Haskell modules are actually very similar to > singletons. Perhaps all these problems with modules having top level > mutable state could be solved if Haskell modules were parameterizable > at "instantiation"? I'm not saying we should turn the Haskell module > system into an OO system, just that maybe it would be wise to borrow > some ideas from that paradigm. Well, I'm a little unclear as to how the discussion shifted from global variables to modules, but as long as we're here: Rather than looking at OO languages, why not take a lesson from more powerful module systems already in functional programming languages. In particular, the ML module system supports "parameterization at instantiation" with functors. Of course, there is considerable evidence that ML modules and Haskell type classes really do the same thing, but they do seem to be useful in very different situations. --Chris

1 0

IO Monad operation madness
by Rob Hoelz 17 May '07

17 May '07

Hello again, I'm still working on that binding, and I've come to a problem that I just can't figure out. I'm sure it's staring me right in the face, so I think another pair of eyes to take a look. So if you look at my previous message, I defined a linked list data type in C. I'm trying to convert it to a Haskell list of strings, so here's my function: linkedListToHaskellStringList :: LinkedList -> IO [String] linkedListToHaskellStringList listPtr = let convertList' ptr = if listIsNull ptr then [] else let str = peekCString =<< (linked_list_getdata ptr) next <- linked_list_next ptr str : (convertList' next) in sequence $ convertList' listPtr listIsNull :: LinkedList -> Bool listIsNull (LinkedList ptr) = ptr == nullPtr So here's the compile error: Option.hsc:63:14: Couldn't match expected type `[t]' against inferred type `IO LinkedList' In a 'do' expression: next <- linked_list_next ptr In the expression: if listIsNull ptr then [] else do let str = peekCString =<< linked_list_getdata ptr next <- linked_list_next ptr str : (convertList' next) In the definition of `convertList'': convertList' ptr = if listIsNull ptr then [] else do let str = ... next <- linked_list_next ptr str : (convertList' next) Could anyone tell me what I'm doing wrong? Thanks a lot! -Rob

2 5

Darcs annotate denies all knowledge of files...
by Dougal Stanton 17 May '07

17 May '07

I just did a fresh pull of hpodder to see if there was still a bug in it that I just found in the feisty version. I ran > $ darcs get --partial http://darcs.changelog.org/hpodder > $ darcs annotate Commands/SetTitle.hs > > darcs failed: There is no file or directory named 'Commands/SetTitle.hs' There is some mention online that Darcs does this when there are special characters in the filename. That isn't the case here. To be certain I ran it on several other files, all with the same result. I ran it on some of my own repositories and it worked fine. What gives? Cheers, Dougal.

3 3

Imagining a G-machine
by Albert Y. C. Lai 17 May '07

17 May '07

A native G-machine --- physical, or chemical, or biological, but not a repressed simulation over the imperative cpu-memory architecture --- is the dream of every lazy-functional programmer of great devotion. If only it became the dominant computing architecture! People would say, Haskell is high-level assembly because it is the closest to the bare metal (or bare protein) and still supports all sorts of abstractions. People would ask, why is my C program five times slower than Haskell, and people would answer, that's because C is compiled to a stack of seven monad transformers (one of which is ContT to support longjmp), and because you should use more linked lists and fewer arrays. We truely rule the world when C programmers have to consult us for performance tips. A necessary condition for dominance is existence. Here is my crazy imagination of a native G-machine. It is worded as biotech but may as well be molecular computing or nanotech. The heap is a soup of nutrients. A node is a molecular structure made from the nutrients. A thunk is a lot of nodes linked up. Nodes and thunks are suspended in the soup. Allocation means constructing nodes and links from nutrients, and deallocation means unlinking nodes and eventually dismantling them back into nutrients. As a side effect, memory upgrade is cheap and convenient: Just go buy a can of Campbell soup (my favourite is the alphabet soup) and pour into your heap. There are 24-hour convenient stores at every street corner --- pervasive computing has never been so pervasive before. A thunk is nodes linked together and suspended in the soup. A theorem in graph theory asserts that all finite graphs can be embedded without crossing edges in 3D space, and we take advantage of this to space out the nodes in a complicated thunk. Still, it is not easy, being NP-hard and all. There is a relaxation heuristic for this: It simply requires nodes to be a bit repulsive to each other and links to be elastic, and they will sort things out themselves. (When they don't, a bit of shaking up helps tremendously.) Evaluation is performed by a small organism crawling over a thunk and performing its thunk-rewriting duty as per the G-machine. It applies enzymes to construct and deconstruct nodes and links from nutrients. It performs primitive arithmetic on its own. It maintains its own stack, inside or outside its body (to be investigated). It is possible to unleash several such evaluators for parallel computing. It is possible to enable reproduction to boost parallelism. To add garbage collection, roots send out a periodic (or sustained) signal to all connected nodes. Nodes receiving the signal do not self-destruct. Nodes not receiving the signal invokes their built-in self-destruct mechanism to dissolve themselves back into nutrients. There may be better schemes. Interacting with the outside world is open, but Andrew Gordon's thesis contains translations from monadic I/O to other I/O schemes, e.g., continuations, streams, etc. Perhaps one of them can be adapted. Debugging can be done by making evaluators send radio signals concerning operations they perform; then a second computer can log these and you can review them. You can also use radio signals to instruct the evaluators to perform unusual operations on demand. The existence of a native G-machine is a necessary but not sufficient condition for world dominance. We still need to make it fast, compact, and cheap. There may also be better but totally different ways to realize a native G-machine.

8 8

Re: Type class help please
by oleg＠pobox.com 17 May '07

17 May '07

Adrian Hey wrote: > -- Instances of GT are instances of Eq -- > instance (GT map key, Eq a) => Eq (map a) where > map1 == map2 = assocsAscending map1 == assocsAscending map2 > ... > Overlapping instances for Eq [(key, a)] > arising from use of `==' at Test.hs:10:16-59 > Matching instances: > instance (Eq a) => Eq [a] -- Defined in GHC.Base > instance (GT map key, Eq a) => Eq (map a) -- Defined at Test.hs:9:0 > > How can my new instance overlap with the old (ghc) instance unless > [] is also an instance of GT for some key type (which it isn't). > Could someone explain? You are right in your explanation of the GHC behavior. Your instance |Eq (map a)| indeed overlaps the `standard` instance |Eq [a]|. The overlap may be easier to see if we write [a] as ([] a), which is what it is, an application of the type constructor [] to the type variable a. So, the type [a] (aka [] a) is a particular instance of the type (map a), with `map' being []. This is the overlapping that GHC is complaining about. Regarding the need for -fallow-undecidable-instance: GHC is not a general purpose termination checker. Furthermore, it seems reasonable for GHC to employ simple termination heuristics, which can be decided quickly, syntactically and locally (that is, considering only the instance in question, rather than collection of all instances in the program). Thus GHC employs a set of heuristics that look if the instance constraints are `smaller' than the instance head. That will assure termination. That criterion is of course not complete, so there are (many) terminating, decidable typeclass program that fail simple GHC termination tests and thus require -fallow-undecidable-instance extension. One method of avoiding overlapping instances is to define a newtype wrapper: newtype MyMap map a = MyMap{unMyMap::map a} class Ord key => GT map key | map -> key where assocsAscending :: map a -> [(key,a)] -- Just 1 of many methods instance GT (MyMap Data.IntMap) Int where ... The drawback is writing MyMap and unMyMap in many places. That spoils the appearance, but rarely fatal. Another solution is replacing the general instance instance (GT map key, Eq a) => Eq (map a) where map1 == map2 = assocsAscending map1 == assocsAscending map2 with its instantiations, for all `maps' in question: instance Eq a => Eq (Data.IntMap a) where ... instance Eq a => Eq (Data.Map key a) where ... instance Eq a => Eq (Data.IntSet a) where ...

2 4

Bad "let..do" syntax
by Chad Scherrer 17 May '07

17 May '07

I've gotten into a habit of preceding most "do"s in my code with a "$", and indenting the next line. I kind of like this, since it makes the indentation more uniform. But it seems to have bitten me now. I'd like to write something like this s = sum $ do x <- [1,2,3] let b = sum $ do y <- [0..x + 1] return y return (x + b) But GHC complains of "Empty 'do' construct". It likes the alternative s' = sum $ do x <- [1,2,3] let b = sum $ do y <- [0..x + 1] return y return (x + b) just fine, but that looks horrible to me (ok, "horrible" is a bit strong, but I don't like it as much). So I'm wondering, (1) Is this intended to give an error, or is it just a momentary hiccup, and (2) if others have run into this, is there a more aesthetic alternative that works? Thanks, Chad

2 2