December 2009 - Haskell-Cafe

Type system speculation
by Andrew Coppin 10 Dec '09

10 Dec '09

People in the Haskell community get awfully excited about Haskell's type system. When I was first learning Haskell, I found this rather odd. After all, a "type" is just a flat name that tells the compiler how many bits to allocate and which operations to allow, right? As I read further, I quickly discovered that in Haskell, the type system is something much more powerful. In a normal language, the type system prevents you from accidentally trying to multiply a string by a binary tree of integers, or pass a function an signed integer when it's expecting an unsigned integer. But in Haskell, the combination of parametric polymorphism, typeclasses and automatic type inference combine to form a potent mixture. Even without any exotic language extensions, in Haskell you can use the type system to *prove stuff about your programs*! And not necessary stuff that's anything to do with the usual notion of a "data type". You can prove that lists are non-empty or even of a specific size. You can prove that optional values get checked before they are used. And you can prove that user input is sanitised before being passed to sensitive functions. (Or rather, you can make your program simply not compile if the required properties are not guaranteed.) Let's take an example. Suppose you have some functions that obtain input from a user, and you have some other functions that do something with this data. What you can do is something like this: newtype Data x y = Data x data Checked data Unchecked check_string :: Data String Unchecked -> Data String Checked Now make it so that everything that obtains data from the user returns Data String Unchecked, and everything that uses a string to do something potentially hazardous demands Data String Checked. (And any functions that don't care whether the string is checked or not can just use Data String x.) Only one problem: Any functions that expect a plain String now won't work. Particularly, the entirity of Data.List will refuse to accept this stuff. Which is kind of galling, considering that a Data String Checked *is* a String! What we're really trying to do here is attach additional information to a value - information which exists only in the type checker's head, but has no effect on runtime behaviour (other than determining whether we *get* to runtime). As far as I can tell, Haskell does not provide any way to take an existing type and attach additional information to it in such a way that code which cares about the new information can make use of it, but existing code which doesn't care continues to work. Any comments on this one? On a rather unrelated note, I found myself thinking about the Type Families extension (or whatever the hell it's called). I found that I can do this: class Collection c where type Element c :: * empty :: c first :: c -> Maybe (Element c) ... This works for collections that can contain *anything*: instance Collection [x] where type Element [x] = x ... It works for collections that can only contain *one* type: instance Collection ByteString where type Element ByteString = Word8 ... And it works for collections that can handle more than one type, but less than *every* type: instance Ord x => Collection (Set x) where type Element (Set x) = x ... Something quite interesting is happening here: this "Element" thing is almost like a *function* which takes one type and returns another. A function that operates on types themselves. Now suppose I want to write a function that converts one kind of collection into another: convert :: (Collection c1, Collection c2) => c1 -> c2 Erm, no. That doesn't work AT ALL. What we want to say is that the element types are constrained (specifically, they're identical). I searched for quite some time looking for a way to say this. In the end, I gave up and let the compiler deduce the type signature automatically. Apparently the correct signature is convert :: (Collection c1, Collection c2, Element c1 ~ Element c2) => c1 -> c2 Apparently the bizare syntax "Element c1 ~ Element c2" means that these two types are supposed to be equal. (Why not just an equals sign?) This got me thinking... Maybe what we'd really like to say is something like convert :: (Collection c1 {Element = x}, Collection c2 {Element = x}) => c1 -> c2 In other words, make the assosiated type like a named field of the class, using syntax similar to the named fields that values can have. And then, if we can do it to classes, why not types? data Map {keys :: *, values :: *} = ... insert :: (Ord k) => k -> v -> Map {keys = k, values = v} -> Map {keys = k, values = v} Now, it seems reasonable that if one of the type fields is unconstrained, you do not need to mention it: keys :: (Ord k) => Map {keys = k} -> [k] values :: Map {values = v} -> [v] If we can have some mechanism for adding new type fields to an existing type, we are one step away from the problem at the beginning. You could take the existing String type, and add (by whatever the mechanism is) a new "safety" field to it. All of Data.List ignores this field, but any new code you write can choose to use it if required. At least, that's my vague idea. Anybody like it? (My first thought is that "Map {keys = k, values = v}" is going to start getting tedious to type very, very quickly. Perhaps we should do something like values :: (m :: Map {values = v}) => m -> [v], or even allow values :: (m :: Map {}) => m -> [values m] as an alternative? IDK.) So there you have it. Multiple paragraphs of semi-directed rambling about type systems. All written by somebody who doesn't even know what a Skolem variable is. :-}

3 2

Re: Are there standard idioms for lazy, pure error handling?
by Henning Thielemann 10 Dec '09

10 Dec '09

Somehow I missed this thread. I want to say that I have implemented a general way to add the information of an exception to the "end" of an arbitrary data structure. http://hackage.haskell.org/packages/archive/explicit-exception/0.1.4/doc/ht… Duncan already mentioned it: > data Exceptional e a = Exceptional { > exception :: Maybe e > result :: a > } > However it's pretty clear from the structure of this type that it cannot > cope with lazy error handling in sequences. If you try it you'll find > you cannot do it without space leaks. Actually you spotted the space leak - but how is it pretty clear, that it has the space leak? I wondered why 'unzip' does not have the space leak, although when I sequence a lot of Exceptional values using mconcat, I'm doing something pretty similar. I also agree with you, that the possibility to access the result directly, and thus easily ignore the exception is bad. I thought it could be improved by removing the field accessors and instead provide the function: switch :: (Maybe e -> c) -> (a -> c) -> Exceptional e a -> c

14 26

Parsec-like parser combinator that handles left recursion?
by Adam Cigánek 10 Dec '09

10 Dec '09

Hello there, Is there some other parser library, with similar nice API than Parsec, but which somehow handles left-recursive grammars? Ideally if it has at least rudimentary documentation and/or tutorial :)

5 5

Re: OpenAL and Hsndfile
by jean legrand 10 Dec '09

10 Dec '09

a while ago, I wrote a minimal and inefficient code to generate and play an audible 4-second-sine sound http://hpaste.org/fastcgi/hpaste.fcgi/view?id=1538 Can you hear something with it ?

1 0

Nano-Languages
by John D. Earle 10 Dec '09

10 Dec '09

What I wrote under "Allowing hyphens in identifiers" and what Richard O'Keefe wrote earlier under "A new form of newtype" caused me to think. It was pointed out that hyphens are not permitted in Haskell identifiers much as they are in Lisp for good cause even though such a feature is regarded by some as especially desirable. It is technically feasible (or at least appears to be). It is a matter of what constitutes good language design. My suggestion was to whip up a makeshift preprocessor to make the necessary substitutions. It might be better to go about it in a fashion similar to how one would use Haskell to create a new language using Happy, but instead of making a full fledged language create a language that makes only minor adjustments to the official language where most of the original source code and command line options are copied verbatim with a handful of things caught such as the Richard O'Keefe newtype, a nano-language if you will. Actually I have known about this possibility for years. There is always something you would like to change about whatever language you are working with and so I have put thought into it. It would make prototyping of new ideas easier. It would furthermore make it possible to make changes that would be unacceptable for an official version of the language such as hyphens in place of underscores for those who feel the benefit of being able to use hyphens this way outweigh the problems it may cause. The official language remains intact. Broadly speaking I am talking about a preprocessor, but one tailored for the needs of Haskell. For related art see Ciao Prolog (see http://ciaohome.org) They are using their preprocessor to do some rather sophisticated things which include program analysis and optimization. Something so elaborate may not be necessary, however. Just some Happy code that has been cobbled together that address some of the issues involved that is reworked to satisfy a special need.

2 3

Re: [Haskell-cafe] forkSequence, runPar, parallelize
by Mario Blažević 10 Dec '09

10 Dec '09

> > > I can't test it right now, but wouldn't the > > following do the job in the Identity monad? > > > forkExec :: Identity a -> Identity (Identity a) > > forkExec k = let result = runIdentity k > > in result `par` return (Identity result) > > > Since Identity is a newtype, would that be equivalent to "result `par` > result"? The forkExec in the IO monad let's other computations keep > going until I need the result from the forked computation. You're right, it doesn't seem to work the way I hoped. The equivalent function on Maybe monad works, though, so it is possible to write forkExec in monads other than IO. > In a pure computation, I can already get the same result with `par` > and laziness, right? Yes. The goal is to enable writing monadic parallel computations which work under any parallelizable monad. For example, I'm using it to run two trampolining producer/consumer coroutines in parallel. A large majority of interesting coroutines I have are completely agnostic with respect to the underlying monad.

1 0

You are in a twisty maze of concurrency libraries, all different ...
by Patrick Caldon 10 Dec '09

10 Dec '09

I'm looking for the "right" concurrency library/semantics for what should be a reasonably simple problem. I have a little simulator: runWorldSim :: MTGen -> SimState -> IO SimState it takes about a second to run on a PC. It's functional except it whacks the rng, which needs IO. I run 5-10 of these jobs, and then use: mergeWorld :: [SimState] -> SimState to pick the best features of the runs and build another possible world (state). Then I use this new world to run another 5-10 jobs and so on. I run this through ~20000 iterations. It's an obvious place for parallelism. I'm looking for a concurrency library with something like: forkSequence :: Int -> [IO a] -> IO [a] which I could call with something like this: forkSequence 4 (take 10 (repeat (runWorldSim g ss))) this would construct 4 threads, then dispatch the 10 jobs onto the threads, and pack up the results into a list I could run through my merger. It strikes me as something someone would already have done, but I can't find anything in hackage. Probably I've missed something obvious? Any pointers? If not, what would be the best/easiest existing package to write an extension to? Thanks, Patrick.

11 14

can there be (hash-table using) O(n) version of this (I think currently) n log n algo?
by Thomas Hartman 09 Dec '09

09 Dec '09

The code below is, I think, n log n, a few seconds on a million + element list. I wonder if it's possible to get this down to O(N) by using a hashtable implemementation, or other better data structure. Further, is there a hashtable implementation for haskell that doesn't live in IO? Maybe in ST or something? import Data.HashTable import qualified Data.Set as S import Data.List (foldl') testdata = [1,4,8,9,20,11,20,14,2,15] ++ [1..(10^6)] wantedsum = 29 -- set data structure -- findsums locates pairs of integers in a list that add up to a wanted sum. findsums :: [Int] -> Int -> S.Set (Int,Int) findsums xs wanted = snd . foldl' f (S.empty,S.empty) $ xs where f (candidates,successes) next = if S.member (wanted-next) candidates then (candidates, S.insert (next,wanted-next) successes) else (S.insert next candidates,successes) -- hashtable data structure -- result: t -- fromList [(15,14),(16,13),(17,12),(18,11),(19,10),(20,9),(21,8),(22,7),(23,6),(24,5),(25,4),(26,3),(27,2),(28,1)] -- probably O(n log n) complexity since using tree based Data.Set (a few seconds on million+ element list) t = findsums testdata wantedsum

9 10

ANNOUNCE: usb-safe-0.1
by Bas van Dijk 09 Dec '09

09 Dec '09

Hello, My usb library provides a standard Haskell abstracting layer over bindings-libusb providing: abstract types instead of Ptrs, automatic marshalling and unmarshalling, automatic garbage collection, exceptions instead of integer return codes, etc.. While all that is very nice there are still some things that you can do wrong. For example doing I/O with a closed device or reading from or writing to an endpoint which doesn't belong to the claimed interface. Or reading from an Out endpoint or writing to an In endpoint. I released the usb-safe package to prevent you making these errors. See: http://hackage.haskell.org/package/usb-safe-0.1 usb-safe provides the following guarantees: - You can't reference handles to devices that are closed. In other words: no I/O with closed handles is possible. - The programmer specifies the region in which devices should remain open. On exit from the region the opened devices are automatically closed. - You can't reference handles to configurations that have not been set. - You can't reference handles to interfaces that have not been claimed. - You can't reference handles to alternates that have not been set. - You can't reference endpoints that don't belong to a setted alternate. - You can't read from an endpoint with an Out transfer direction. - You can't write to an endpoint with an In transfer direction. - You can't read from or write to endpoints with the unsupported transfer types Control and Isochronous. Only I/O with endpoints with the Bulk and Interrupt transfer types is allowed. The primary technique used in usb-safe is called "Lightweight monadic regions" which was invented by Oleg Kiselyov and Chung-chieh Shan. See: http://okmij.org/ftp/Haskell/regions.html#light-weight Note that I consider this a preview release. In fact, I haven't tested the package at all. I can only guarantee you that it will pass the type-checker. As always: questions, comments and patches are more than welcome. Please don't look at the hscolour generated source code from the haddock documentation because it screws up the nice unicode symbols I used. If you want to read the source download the package or go straight to the darcs repos: darcs get http://code.haskell.org/~basvandijk/code/usb-safe regards, Bas

1 2

pexports Was: Re: [Haskell-cafe] binding to C libraries on Windows was Low Level Audio - Writing bytes to the sound card?
by Stephen Tetley 09 Dec '09

09 Dec '09

Hi All, Would a pure Haskell version of pexports be useful to the Haskell community? For a Sunday afternoon hack that turned out to take a bit more effort (its now Wednesday), I thought I'd code up a tool that extracts function symbols from .dll's (also when I first looked at the C pexports it seemed somewhat unadopted, though checking today it appears to in MinGW, so my local MinGW must be out-of-date). If there are compelling uses that aren't covered by pexports and would ease Haskell C binding problems on Windows, I don't mind polishing up my tool, but otherwise I've exhausted my natural interest. Best wishes Stephen

3 3