- Haskell-Cafe - Haskell.org

Tutorial for using the state monad or a better suggestion?
by Jefferson Heard 22 Feb '08

22 Feb '08

So the reason I keep pinging the list so much of late is I'm currently writing a GLUT program to visualize a heirarchical clustering of 18,000+ protein-protein interaction pairs (and associated gene-ontology terms). Thanks for the help on reading CSVs, those who wrote me back... my program intitializes and displays its first image within 6 seconds, about 10 times faster and in 10 times less memory than the Java program the guy was using. Now I'm to the point of making this thing interactive, and I I'm trying to figure out the Haskell way of doing this. Last time I wrote a program like this, I made a record data type with all the state and placed it into an IORef and curried it into the GLUT callback functions. I'm going to do the same thing now if there aren't cringes and wailings from people with a better sense of pure-functional aesthetics out there on the list with a willingness to either point me towards a tutorial that would help me do this better. Keep in mind that Graphics.UI.GLUT callbacks all want to return an IO (), and thus leftover state monads at ends of functions aren't going to be acceptable to the standard library... Any ideas? Oh, currently my program state includes: The geometry I'm rendering (Ptr GLfloat vertex and color arrays), The same geometry as a display list for rendering into the selection buffer An indexed and named tree that represents the clustering A tree of text containing tooltips to display The previous current mouse position (for dragging purposes) A couple of histograms as Array.IArray.Diff.DiffArrays Various parameters for constructing rendered data out of the indexed tree (for reconstruction after a node is collapsed/expanded) So I'm carrying around some pretty bulky state; should give you some understanding as to why I thougt the record data type would be the sanest way to do this without polluting my parameter list with individual IORrefs. Oh, and again, it's not that I don't know that I can make the IORef solution work, I can and I've done it before. It's just that I thought there might be a prettier way to do this. Thanks in advance! -- Jeff

4 4

Tips of Conditional Expression
by TOPE KAREM 22 Feb '08

22 Feb '08

I know the following: [1] That the general form of conditional expression is: if * Boolean_expression* then *exp1* else *exp2 *[2] That a conditional expression must always have both a then and an elseexpression. [3] That both *exp1* and *exp2* must have the same type, which is the type of the entire conditional expression. [4] That *exp1* must be <true-value> and *exp2* must be <false-value> Reference: Discrete Mathematics Using Computer by John O'Donnell and et al. (Second Edition) My question: Is it possible that exp1 and exp 2 be different function calls of another functions (separately) elsewhere within the same program? Note: My Boolean_expression is Boolean My *exp1* is a function call elsewhere within the same program (more like a subroutine) My *exp2* is another function call also elsewhere within the same program. Tope South Africa

3 5

The Proliferation of List-Like Types
by John Goerzen 22 Feb '08

22 Feb '08

Hi folks, Before I started using Haskell, I used OCaml for a spell. One of my biggest annoyances with OCaml was that it had two list types: the default list (strict), and a lazy list (known as a stream). This led to all sorts of annoyances. Libraries were always written to work with one list or the other. If you wanted to use two libraries, one that assumed one list and the other that assumed another, you had a difficult task ahead of you. I am concerned that the same thing is happening in Haskell. We know have three common list-like types: the regular list, strict ByteString, and lazy ByteString. This has created some annoying situations. For instance, a ByteString is great for reading data fast, but Parsec doesn't work on ByteStrings. I am glad that someone wrote a Parsec equivolent that does[1], which answers a real need. But this means that all the combinators in the hsemail library that implement standard RFC conventions won't be usable in my ByteString code, for instance. Similarly, we have another annoying situation relating to character encodings: * The iconv library works only on lazy ByteStrings, and does not handle Strings or strict ByteStrings * The utf8-string library doesn't support UTF-16, doesn't require an external library, and works only on Strings -- no support for ByteStrings. * Data.Encoding.* is native haskell, supports UTF-*, but works only on ByteSting.Lazy again. Now, to help solve this problem, I wrote ListLike[2], providing a set of typeclasses that make list operations generic. I also provided default instances of ListLike for: ListLike Data.ByteString.ByteString Word8 ListLike Data.ByteString.Lazy.ByteString Word8 ListLike [a] a (Integral i, Ix i) => ListLike (Array i e) e (Ord key, Eq val) => ListLike (Map key val) (key, val) These instances use the native underlying calls where appropriate (for instance, ByteString and Data.List both provide a 'head'). The typeclass also contains large numbers of default implementations, such that only four functions must be implemented to make a type a member of ListLike. API ref is at http://software.complete.org/listlike/static/doc/ListLike/Data-ListLike.htm… Now, the questions: 1) Does everyone agree with me that we have a problem here? 2) Would it make sense to make ListLike, or something like it, part of the Haskell core? 3) Would it make sense to base as much code as possible in the Haskell core areound ListLike definitions? Here I think of functions such as lines and words, which make sense both on [Char] as well as ByteStrings. 4) We are missing one final useful type: a Word32-based ByteString. When working in the Unicode character set, a 32-bit character can indeed be useful, and I could see situations in which the performance benefit of a ByteString-like implementation could be useful combared to [Char]. [1] Yes, I have read about Parsec 3 being imminent, which is also great [2] http://software.complete.org/listlike

16 41

Re: [Haskell-cafe] Can't seem to get `par` working appropriately with lists
by Luke Andrew 22 Feb '08

22 Feb '08

Felipe Lessa wrote: > On Thu, Feb 21, 2008 at 8:58 AM, Luke Andrew <luke.haskell-cafe(a)la.id.au> wrote: > >> test2.hs: >> >> import Control.Parallel >> >> fib1 n = if n == 0 then 0 else if n == 1 then 1 else fib1 (n-1) + >> fib1 (n-2) >> fib2 n = if n == 0 then 0 else if n == 1 then 1 else fib2 (n-1) + >> fib2 (n-2) >> fiblist1 n = [fib1 x| x <- [1..n]] >> fiblist2 n = [fib2 x| x <- [1..n]] >> >> main = do print $ zipWith (+) (fiblist2 37 `par` fiblist1 37) >> (fiblist2 37) >> > > Besides what Jules Bean said, note also that 'par' works a bit like > 'seq', only evaluating until WHNF. So even if you said > > main = > let f1 = fiblist1 37 > f2 = fiblist2 37 > in print $ zipWith (+) (f2 `par` f1) f2 > > you still wouldn't get what you want. Why? It only evaluates f1 and f2 > until it reaches [] or (_:_), and nothing more, it doesn't even try to > figure out that f2 is _:_:_:_:···:[] nor it tries to see that f2 is > 1:_, but you wanted that the parallel computation went until f2 was > 1:1:2:3:···:[]. > > To do that, force the list (i.e. do a "deep seq"). There's > Control.Parallel.Strategies to help you doing this, but if you want to > reimplement it, try > > force [] = () > force (x:xs) = x `seq` force xs > > main = > let f1 = fiblist1 37 > f2 = fiblist2 37 > in print $ zipWith (+) (force f2 `par` f1) f2 > > 'par' will try to see that 'force f2' is really (), but to do that > 'force' will go all the way down thru the list forcing its spine and > its values. > > HTH, > > Thanks Felipe, works as advertised. Guest I'm going to have to read up on WHNF, I just ignored it after my initial success & hoped it would continue to work. Guess I should have RTFM :)

1 0

Re: [Haskell-cafe] Selecting Array type
by Ryan Ingram 22 Feb '08

22 Feb '08

On 2/21/08, Jeff φ <jeff1.61803(a)gmail.com> wrote: > Thanks again. I'm not familiar with type equality constraints. I could not > find information on this in the GHC users guide. Is it documented > somewhere? Section 7.3 here talks about equality constraints. http://www.haskell.org/haskellwiki/GHC/Indexed_types There's an extremely good paper talking about the low-level mechanisms for equality constraints in GHC Core here: http://research.microsoft.com/%7Esimonpj/papers/ext%2Df/ GHC Core -is- System Fc as described in that paper; the type equality constraints amount to a "coercion" function that is passed around the core language to convert between the types and which is statically guaranteed to be the identity function. > It is interesting that you were able to drop the IArray > constraint from the instances of SmartArraySelector. During compilation from Haskell to Core, the compiler implicitly adds calls to any available conversion functions it knows about as required to convert between types. This is why the IArray declaration can be dropped; the compiler looks at the coercions currently available, finds (a ~ UArray), and inserts a call that converts the existing "IArray UArray Bool" declaration into an "IArray a Bool" declaration. Determining that such a path exists is a search problem and much of the work with associated types and type equality constraints involves proving that the search is decidable. -- ryan

1 0

Can't seem to get `par` working appropriately with lists
by Luke Andrew 22 Feb '08

22 Feb '08

Hopefully an easy one here; after reading Don Stewart's blog posts about parallel Haskell and with a shiny new quad-core cpu begging for a workout, i thought I'd give Haskell a try. I've also been meaning to write a ray-tracer, so I started with that. I've got the initial ray-tracer working, and am now looking to parallize it. I tried using the `par` function to evaluate things in parallel, but I couldn't get it to work with lists. I simplified my problem down into the following 2 test cases: (there are two fibonacci functions to ensure haskell treats them as 2 independent computations to be spread across 2 cores) test1.hs: import Control.Parallel fib1 n = if n == 0 then 0 else if n == 1 then 1 else fib1 (n-1) + fib1 (n-2) fib2 n = if n == 0 then 0 else if n == 1 then 1 else fib2 (n-1) + fib2 (n-2) main = do print $ (fib2 37 `par` fib1 37) + (fib2 37) compilation & testing: luke@Sonata:~/mcls$ ghc -O2 -threaded --make test1 [1 of 1] Compiling Main ( test1.hs, test1.o ) Linking test1 ... luke@Sonata:~/mcls$ time ./test1 +RTS -N1 48315634 real 0m5.856s user 0m5.816s sys 0m0.004s luke@Sonata:~/mcls$ time ./test1 +RTS -N2 48315634 real 0m3.450s user 0m6.734s sys 0m0.024s As expected, running it with 2 cores is substantially faster. Doing almost the same thing, but with lists, doesn't seem to have any significant speed difference: test2.hs: import Control.Parallel fib1 n = if n == 0 then 0 else if n == 1 then 1 else fib1 (n-1) + fib1 (n-2) fib2 n = if n == 0 then 0 else if n == 1 then 1 else fib2 (n-1) + fib2 (n-2) fiblist1 n = [fib1 x| x <- [1..n]] fiblist2 n = [fib2 x| x <- [1..n]] main = do print $ zipWith (+) (fiblist2 37 `par` fiblist1 37) (fiblist2 37) compilation & testing: luke@Sonata:~/mcls$ ghc -O2 -threaded --make test2 luke@Sonata:~/mcls$ time ./test2 +RTS -N1 [2,2,4,6,10,16,26,42... ...405774,18454930,29860704,48315634] real 0m15.294s user 0m15.196s sys 0m0.013s luke@Sonata:~/mcls$ time ./test2 +RTS -N2 [2,2,4,6,10,16,26,42... ...405774,18454930,29860704,48315634] real 0m15.268s user 0m15.169s sys 0m0.013s I've tried using bang patterns in various places, but to no avail. Any ideas? Luke Andrew.

4 3

Re: [Haskell-cafe] Selecting Array type
by Jeff φ 21 Feb '08

21 Feb '08

On 2/19/08, Ryan Ingram <ryani.spam(a)gmail.com> wrote: > > Oleg's done a lot of work here; there's a bunch of magic that can be > done with TypeCast. I took my inspiration from here: > http://okmij.org/ftp/Haskell/typecast.html#ambiguity-resolution > . . . > > The trick is to represent whether a type is boxed or not via a > type-level boolean, which you can then use to affect the instance > selecton. > . . . > > -- Magic toolbox that solves everything! Thanks Oleg! > > data HTrue > data HFalse > > class TypeCast a b | a -> b, b->a where typeCast :: a -> b > class TypeCast' t a b | t a -> b, t b -> a where typeCast' :: t->a->b > class TypeCast'' t a b | t a -> b, t b -> a where typeCast'' :: t->a->b > instance TypeCast' () a b => TypeCast a b where typeCast x = typeCast' () > x > instance TypeCast'' t a b => TypeCast' t a b where typeCast' = typeCast'' > instance TypeCast'' () a a where typeCast'' _ x = x > Thanks for showing me this technique. I studied your code for several hours. And, I've read Oleg's "Strongly Typed Heterogeneous Collections." As a learning exercise, I modified your code. I managed to shorten it a bit, but I had a couple of surprises. Please see my comments in the code below. {-# OPTIONS_GHC -fglasgow-exts -fbreak-on-exception -fallow-undecidable-instances -fallow-overlapping-instances #-} module SmartArray where import IO import Data.Ix import Data.Array.Unboxed import Data.Complex type SmartArray i e = (Ix i, SmartArraySelector a e) => (a i e) -- smartArray is similar to array function from Data.Array. But, -- it will return a UArray if e can be unboxed. Otherwise, it -- returns an Array. smartArray :: (i, i) -> [(i, e)] -> SmartArray i e smartArray bnd eLst = array bnd eLst class ArrTypeCast a b | a -> b, b->a where arrTypeCast :: a i e -> b i e instance ArrTypeCast x x where arrTypeCast = id -- SURPRISE 1: If function, arrTypeCast, is removed, (from both -- the class and instance) GHC assumes the kind of a and b are *, -- instead of * -> * -> * and produce . . . -- -- report3.hs:37:24: -- `UArray' is not applied to enough type arguments -- Expected kind `*', but `UArray' has kind `* -> * -> *' -- In the type `(ArrTypeCast a UArray, IArray a Bool) => -- SmartArraySelector a Bool' -- In the instance declaration for `SmartArraySelector a Bool' -- -- It appears that functions defined in a class can constrain the -- type variables of the class. To me, this seems a bit magical -- and unexpected. class (IArray a e) => SmartArraySelector a e | e -> a -- instances of SmartArraySelector for all boxed types (For -- breivity, not all unboxed types are listed.) instance (ArrTypeCast a UArray, IArray a Bool) => SmartArraySelector a Bool instance (ArrTypeCast a UArray, IArray a Char) => SmartArraySelector a Char instance (ArrTypeCast a UArray, IArray a Double) => SmartArraySelector a Double instance (ArrTypeCast a UArray, IArray a Float) => SmartArraySelector a Float instance (ArrTypeCast a UArray, IArray a Int) => SmartArraySelector a Int -- SURPRISE 2: The class SmartArraySelector has the type -- assertion, (IArray a e). It seems like adding an additional -- IArray assertion to each instance is redundant. However, -- if I remove the assertion (IArray a Int) above, GHC -- reports . . . -- -- report3.hs:37:24: -- `UArray' is not applied to enough type arguments -- Expected kind `*', but `UArray' has kind `* -> * -> *' -- In the type `(ArrTypeCast a UArray, IArray a Bool) => -- SmartArraySelector a Bool' -- In the instance declaration for `SmartArraySelector a Bool' -- -- Why is this second type assertion required? instance (ArrTypeCast a Array, IArray a b) => SmartArraySelector a b test :: SmartArraySelector a e => e -> a Int e test e = smartArray (0,10) [ (i,e) | i <- [0..10]] I'd love to find a good article that describes the ins and outs of multi parameter types, functional dependencies, and type assertions, in enough detail to resolve these surprises. A step-by-step walk through showing how the compiler resolve a type and selects an instance would be awesome. Usually, when I'm having trouble getting Haskell's type system to do what I want, I resort to trial and error tactics. I wish I had a better foundation so I could take a more intelligent approach to type hacking.

3 2

Repeated function application
by Ben Butler-Cole 21 Feb '08

21 Feb '08

Hello I was surprised to be unable to find anything like this in the standard libraries: times :: (a -> a) -> Int -> (a -> a) times f 0 = id times f n = f . (times f (n-1)) Am I missing something more general which would allow me to repeatedly apply a function to an input? Or is this not useful? I thought this looked a bit like a fold, so I tried expressing it like this: times f n x = foldl (flip ($)) x (replicate n f) ... which horrifies me, but I can't help feeling that there must be a way to get rid of the explicit recursion. How would you implement times? Ben

4 3

Problem with Python AST
by Roel van Dijk 21 Feb '08

21 Feb '08

Hello everyone, I am trying to create an AST for Python. My approach is to create a data type for each syntactic construct. But I am stuck trying to statically enforce some constraints over my statements. A very short example to illustrate my problem: newtype Ident = Id String data BinOp = Add | Sub data Exp = IntLit Integer | BinOpExp BinOp Exp Exp data NormalCtx data LoopCtx data Statement ctx where Compound :: Compound -> Statement ctx Pass :: Statement ctx Break :: Statement LoopCtx newtype Global = Global [Ident] data Suite ctx = Suite [Global] [Statement ctx] type Else = Suite NormalCtx data Compound = If [(Exp, Suite NormalCtx)] (Maybe Else) | While Exp (Suite LoopCtx) (Maybe Else) newtype Program = Program [Statement NormalCtx] The "global" statement makes an identifier visible in the local scope. It holds for the entire current code block. So it also works backwards, which is why I didn't make it a statement but part of a suite (= block of statements). Some statements may occur in any context, such as the "pass" statement. But others are only allowed in certain situations, such as the "break" statement. This is why I defined the Statement as a GADT. I just supply the context in which the statement may be used and the typechecker magically does the rest. Feeling very content with this solution I tried a slightly more complex program and discovered that my AST can not represent this Python program: for i in range(10): if i == 6: break The compound if statement is perfectly valid nested in the loop because the Compound constructor of Statement allows any context. But the suites inside the clauses of the if statement only allow normal contexts. Since Break has a LoopCtx the typechecker complains. Is there some other way to statically enforce that break statements can only occur _nested_ inside a loop? There is a similar problem with return statements that may only occur in functions. These nested statements should somehow 'inherit' a context, if that makes any sense :-) I know I can simply create separate data types statements that can occur inside loops and function bodies. But that would make the AST a lot more complex, something I try to avoid. Python's syntax is already complex enough! Most of these constraints are not in the EBNF grammar which can be found in the language reference, but they are specified in the accompanying text. The cpython interpreter will generate SyntaxError's when you violate these constraints. See also Python's language reference: http://docs.python.org/ref/ref.html (see sections 6 and 7)

2 2

stream/bytestring questions
by Chad Scherrer 21 Feb '08

21 Feb '08

ByteStrings have given a real performance boost to a lot of Haskell applications, and I'm curious why some of the techniques aren't more abstracted and widely available. If it's "because it's a big job", that's certainly understandable, but maybe there's something I'm overlooking that some of the abstractions aren't really desirable. My first question is about the stream fusion. This seems (based on the ByteString paper) to speed things up quite a lot, but for some reason this isn't necessarily the case for lists. Is this just a matter of the existing fusion for lists doing such a good job in many cases that it's hard to beat? The streams paper suggests that some contructors aren't optimized away during fusion, but wouldn't this also be a problem for fusion in the bytestring context? Are there many cases where it helps performance to program to streams directly, rather than letting the rules go back and forth between them and lists? I tried to do this, but kept getting hung up on the Unlifted stuff; it's not exposed (pardon the pun) in the API, and I don't understand why the types are different than the usual (), Either a b, (a,b), etc. Second, the idea of representing a sequence as a lazy list of strict arrays is very appealing. But why represent it so concretely? Wouldn't it make sense to do something like data ArrayList a i e = Empty | Chunk !(a i e) (ArrayList a i e) ? Then array fusion could be written for IArray types in general, and the ByteString library would become a set of instances with some specialization pragmas. Presumably a more general StorableVector could be represented as an IArray, and the NDP stuff seems a good fit too, so this would make it easy to leverage future work. Seems to separate the various concerns a little better, too, but again maybe there's a performance issue I'm missing. Sorry for the barrage of questions; I guess there's just a lot I'm trying to understand better. Thanks, Chad

5 12