March 2006 - Haskell-Cafe

Learning from scratch
by Xavier Elizalde 16 Mar '06

16 Mar '06

I'm just starting to learn Haskell from scratch and I've just hit a snag. The book "Haskell: The Craft of Functional Programming, Second Edition" uses some examples that call functions from Prelude.hs. But for some reason, two installations of Haskell that I have on my computer don't have the functions available. I have the OS X version of Hugs (http://www.haskell.org/soe/software.htm) for the book "The Haskell School of Expression" installed, as well as the latest version of the Glasgow Haskell Compiler. Both of them get errors with the functions such as "ord" and "chr" mentioned at the beginning of the first book mentioned. Where can I get Prelude.hs and the other files it needs, and what do I do with them? I'm going to move on to the School of Expression book after the Craft of Functional Programming book, which is why I have the SOE version of hugs installed.

2 1

(no subject)
by José Miguel Vilaça 15 Mar '06

15 Mar '06

Hi Im having a small problem with the portability of my Haskell code. My code uses wxHaskell and the library for which this one is the Haskell interface (that is called wxWidgets) doesnt work in the same away in Windows and Linux. Now I now which code run in Linux and in Windows but I dont want to have to manually change the file in each platform. I tried a solution using the C pre-processor but I getting in trouble. I use code like: #ifdef __WIN32__ (Windows code) #else (Linux code) #endif I also add the --cpp to the ghc and it works for me in Linux but give me linking errors in Windows. Does someone have any hints on how to have different code in Windows and Linux? I would be thankful in some help. Best regards Miguel Vilaça

2 1

request for code review
by Shannon -jj Behrens 15 Mar '06

15 Mar '06

Hi, I'm working on another article like <http://www.linuxjournal.com/article/8850>. This time, I'm taking an exercise out of "Expert C Programming: Deep C Secrets" and translating it into Haskell. The program translates C type declarations into English. I would greatly appreciate some code review. I'd prefer to look like an idiot in front of you guys rather than in front of everyone in the world! ;) Please understand, I am not a Haskell expert! Therefore, please make your suggestions simple enough that I can actually accomplish them! By the way, my code *mostly* follows the code laid out in the book. I don't use a lexer or a parser or greatly improve on his algorithm. I'd like the Haskell and C versions to be similar so that they can be compared. The C version is: <http://www.cs.may.ie/~jpower/Courses/compilers/labs/lab3/parse_decl.c> The Haskell version is below. Thanks! -jj {- Translate C type declarations into English. This exercise was taken from "Expert C Programming: Deep C Secrets", p. 84. Example: echo -n "int *p;" | runhugs cdecl.hs Name: Shannon -jj Behrens <jjinux(a)gmail.com> Date: Fri Feb 17 00:03:38 PST 2006 -} import Char (isSpace, isAlphaNum, isDigit) -- |> is like a UNIX pipe. infixl 9 |> x |> f = f x data TokenType = Identifier | Qualifier | Type | Symbol Char deriving (Show, Eq) data Token = Token { tokenType :: TokenType, tokenValue :: String } deriving Show data ParseContext = ParseContext { input :: String, -- The input that has not been parsed yet. output :: [String], -- A list of strings in the reverse order of that which -- they should be printed (e.g. [" a dog.", "I have"]). currTok :: Token, -- The current token, if defined. stack :: [Token] -- A stack of tokens we haven't dealt with yet. } deriving Show -- For convenience: currTokType :: ParseContext -> TokenType currTokType ctx = ctx |> currTok |> tokenType currTokValue :: ParseContext -> String currTokValue ctx = ctx |> currTok |> tokenValue type ParseContextTransformation = ParseContext -> ParseContext -- Start a new ParseContext given an input string. createParseContext :: String -> ParseContext createParseContext input = ParseContext {input=input, output=[], stack=[]} -- Create the final output string given a ParseContext. consolidateOutput :: ParseContext -> String consolidateOutput ctx = ctx |> output |> reverse |> concat {- "Write" to a ParseContext's output. The API is a bit strange. (writeOutput s) is itself a ParseContextTransformation which you can apply to ParseContexts. Strange but convenient. -} writeOutput :: String -> ParseContextTransformation writeOutput s = \ctx -> let newOutput = s : (output ctx) in ctx {output=newOutput} -- Return the top token on the stack. stackTop :: ParseContext -> Token stackTop ctx = let (x:xs) = stack ctx in x -- Pop the stack. pop :: ParseContextTransformation pop ctx = let (x:xs) = stack ctx in ctx {stack=xs} -- Write the value of the top of the stack and then pop it. popAndWrite :: ParseContextTransformation popAndWrite ctx = ctx |> ((stackTop ctx) |> tokenValue |> writeOutput) |> pop -- Classify a string into a Token. classifyString :: String -> Token classifyString "const" = Token Qualifier "read-only" classifyString "*" = Token (Symbol '*') "pointer to" classifyString s@(c:[]) | not (isAlphaNum c) = Token (Symbol c) s classifyString s = Token (whichType s) s where whichType "volatile" = Qualifier whichType "void" = Type whichType "char" = Type whichType "signed" = Type whichType "unsigned" = Type whichType "short" = Type whichType "int" = Type whichType "long" = Type whichType "float" = Type whichType "double" = Type whichType "struct" = Type whichType "union" = Type whichType "enum" = Type whichType _ = Identifier -- Read the next token into currTok. getToken :: ParseContextTransformation getToken ctx@(ParseContext {input=s}) = let lstrip s = dropWhile isSpace s (token, theRest) = s |> lstrip |> lexString in ctx {currTok=token, input=theRest} -- Read a token. Return it and the left-over portion of the string. lexString :: String -> (Token, String) lexString s@(c:cs) | isAlphaNum c = let (tokString, theRest) = span isAlphaNum s token = classifyString tokString in (token, theRest) lexString ('*':cs) = (classifyString "*", cs) lexString (c:cs) = (classifyString (c:[]), cs) -- Put tokens on the stack until we reach the first identifier. readToFirstIdentifier :: ParseContextTransformation readToFirstIdentifier ctx = let afterIdentifier = ctx |> getToken |> pushUntilIdentifier identifier = afterIdentifier |> currTokValue s = identifier ++ " is " in (afterIdentifier {output=[s]}) |> getToken -- Keep pushing tokens until we hit an identifier. pushUntilIdentifier :: ParseContextTransformation pushUntilIdentifier ctx | currTokType ctx == Identifier = ctx | otherwise = let newStack = (currTok ctx) : (stack ctx) in (ctx {stack=newStack}) |> getToken |> pushUntilIdentifier -- Deal with arrays. dealWithArrays :: ParseContextTransformation dealWithArrays ctx = let writeIfNumber ctx = -- Call writeSize if a number. if ctx |> currTokValue |> (!! 0) |> isDigit then ctx |> writeSize |> getToken else ctx writeSize ctx = -- Output the array size. let num = ctx |> currTokValue |> read |> (+ -1) |> show s = "0.." ++ num ++ " " in ctx |> (writeOutput s) in case currTokType ctx of Symbol '[' -> ctx |> (writeOutput "array ") |> getToken |> writeIfNumber |> getToken |> (writeOutput "of ") |> dealWithArrays _ -> ctx -- Recurse until we get past the ['s. -- Deal with function arguments. dealWithFunctionArgs :: ParseContextTransformation dealWithFunctionArgs ctx = let getUntilParen ctx = -- Read tokens until we hit ). case currTokType ctx of Symbol ')' -> ctx _ -> ctx |> getToken |> getUntilParen in ctx |> getUntilParen |> getToken |> (writeOutput "function returning ") -- Deal with pointers. dealWithPointers :: ParseContextTransformation dealWithPointers ctx = case ctx |> stackTop |> tokenType of Symbol '*' -> ctx |> popAndWrite |> (writeOutput " ") |> dealWithPointers _ -> ctx -- Recurse until we get past the *'s. -- Process tokens that we stacked while reading to identifier. dealWithStack :: ParseContextTransformation dealWithStack ctx = case stack ctx of [] -> ctx (x:xs) -> case tokenType x of Symbol '(' -> ctx |> pop |> getToken |> dealWithDeclarator _ -> ctx |> popAndWrite -- Do all parsing after first identifier. dealWithDeclarator :: ParseContextTransformation dealWithDeclarator ctx = ctx |> (case currTokType ctx of Symbol '[' -> dealWithArrays Symbol '(' -> dealWithFunctionArgs _ -> id) |> dealWithPointers |> dealWithStack -- Translate a C type declaration into English. translate :: String -> String translate s = s |> createParseContext |> readToFirstIdentifier |> dealWithDeclarator |> consolidateOutput -- Change this to "show" to debug. -- Main main :: IO () main = do input <- getContents input |> translate |> putStrLn

12 20

Deepest functor [was: fmap for lists of lists of lists of ...]
by oleg＠pobox.com 15 Mar '06

15 Mar '06

Greg Buchholz wrote: > Is it possible to make a typeclass like Functor, that has a function > (say "f_map"), which would work for the infinite hierarchy of types: > ([],[[]],[[[]]],...)? You do understand that this requires overlapping instances? Because the type [[Bool]] is still a list. In general, an instance that matches on the type [[a]] will also match [[[a]]], etc. That's where the IsFunction-like trick comes in handy. Please note that the overlapping instances are only needed for the implementation of the IsCollection predicate. The typeclass for the deep Funct needs no overlapping instances. The code below is more general that required. It also generic: it works for any Functor and any combination of Functors. It performs fmap over arbitrarily deep `collections': lists of maybes of maps of IOs, etc. -- arbitrarily nested fmappable things. test3 = f_map not (Just [Just True, Nothing]) test4 = f_map not (print "here" >> return (Just (Just [Just [True], Nothing]))) >>= print > {-# OPTIONS -fglasgow-exts #-} > {-# OPTIONS -fallow-undecidable-instances #-} > {-# OPTIONS -fallow-overlapping-instances #-} > > module FMAP where > > data Atom > > -- Check if a type is a collection type. This is the only typeclass that > -- needs overlapping instances > class IsCollection t coll | t -> coll > instance IsCollection (m a) (m ()) > instance TypeCast Atom coll => IsCollection t coll > > -- our common working horse > 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 > > -- The desired deep functor. Needs no overlapping instances > class Funct a b c1 c2 | c1 -> a, c1 b -> c2 where > f_map :: (a -> b) -> c1 -> c2 > > instance (IsCollection c1 coll, Funct' coll a b c1 c2) > => Funct a b c1 c2 where > f_map = f_map' (undefined::coll) > > class Funct' coll a b c1 c2 | coll c1 -> a, coll c1 b -> c2 where > f_map' :: coll -> (a -> b) -> c1 -> c2 > > instance Funct' Atom a b a b where > f_map' _ = id > > instance (Functor m, Funct a b c d) => Funct' (m ()) a b (m c) (m d) where > f_map' _ = fmap . f_map > > > test1 = f_map (+1) [[[1::Int,2,3]]] > test2 = f_map not [[True], [False]] > test3 = f_map not (Just [Just True, Nothing]) > test4 = f_map not (print "here" >> > return (Just (Just [Just [True], Nothing]))) > >>= print

3 2

More STUArray questions
by Martin Percossi 15 Mar '06

15 Mar '06

Hello, I am trying to write a haskell-native matrix library (providing a similar set of functionality as gsl's matrix/eigenvector routines). I have had a look at other attempts at matrix libraries, and have found Hal Daume's and Alberto Ruiz's libraries to offer a good amount of functionality. There are two major reasons for wanting to write my own library: 1. Haskell-nativeness: I have had some issues compiling and linking with gsl libraries on 64-bit platforms. Also, it would be quite interesting to gauge haskell's effectiveness as a scientific computing platform, in particular making use unboxed arrays as representation. 2. Use of monads: in the afore-mentioned libraries, monads are either ignored, or are restricted to the IO monad. I am taking a different approach, starting my code from the ST monad, and eventually this will be generalized to work with the IO monad. I think the ST monad is a good monad to be able to perform computations on matrices that update them, allowing efficient, in-place algorithms, but it also provides the benifit of not being a one-way street like the IO monad is. Being a relative newcomer to haskell, I would be interested to hear any thoughts as to whether this is a good/bad idea. Now to my question: I would like to represent a matrix as a wrapper around a block, which in turn is just an unboxed array. Here are the definitions for a matrix in ST and outside of a monad, respectively: type MBlock s = STUArray s Int Double data MMatrix s = MMatrix Int Int (MBlock s) type Block = UArray Int Double data Matrix = Matrix Int Int Block Now, I have started by providing some fairly low-level routines in the ST monad. My problem is depressingly simple: I would like to retrieve a matrix from the ST monad for use outside of it (in particular, to pretty-print it). Now, this is easy for STUArrays (just use runSTUArray), but I'm not sure of how to do it for a type that *encloses* an STUArray. For example, here's a simple test: runMatrix = do _A <- newListMatrix [[2, 0, 0], [0, 2, 0], [0, 0, 2]] _B <- newListMatrix [[1, 2, 1], [0, 1, 1], [0, 0, 1]] _C <- matMul _A _B return $ getBlock _C main = show $ runSTUArray runMatrix Obviously, what I get as a result of runSTUArray is a UArray, which is a pain because I'd then have to box it "by hand" (i.e. again specifying the number of rows and columns), instead of automatically, in order to have a Matrix again. So what I'd like is a runSTMatrix routine, which would possibly have signature: runSTMatrix :: ST s (Matrix s) -> Matrix which would have semantics analogous to runSTUArray. Does anyone have any idea of how I can write runSTMatrix? Many thanks in advance, Martin

5 10

fmap for lists of lists of lists of ...
by Greg Buchholz 15 Mar '06

15 Mar '06

Is it possible to make a typeclass like Functor, that has a function (say "f_map"), which would work for the infinite hierarchy of types: ([],[[]],[[[]]],...)? Does that make sense? This doesn't work... >class Funct f where > f_map :: (a -> b) -> f a -> f b > >instance Funct [] where > f_map = map > >instance Funct a => Funct [a] where > f_map f = map (f_map f) > >main = print $ fmap (+1) [[[1,2,3]]] ...but maybe it gets the idea across? Thanks, Greg Buchholz

1 0

GUI-Woes
by Daniel Fischer 15 Mar '06

15 Mar '06

Hello All, how would I get myself a working (and easy to use) GUI-library? Fudgets looks good, but I couldn't get it to build. I downloaded the snapshot from 2005, how to compile says make ghc-all; make ghc-install, but it doesn't work. First, in several scripts/makefiles, the ghc version 4.06 was hardwired, after some editing make complained about not finding lmlmk, whatever that is. If that's all that I would need to build it successfully, where would I get it? I also tried FranTk, doesn't look bad either, but has ghc -version 4.04 hardwired, imports IOExts, which I think would have to be replaced with GHC.Exts, and Addr, which I have no clue what it should be now, anyway, it seems pre-hierarchical-libraries, which would mean a lot of editing the source-files. So, since Fudgets does work in principle, - which version should I use and where do I get it? - what else would I have to download to get it to build? - in case it isn't straightforward, how to build it? I have a linux machine with ghc-6.4.1 and hugs, no HBC, NHC, JHC,..., no GTk2hs (would I need that?). Thanks, Daniel -- "In My Egotistical Opinion, most people's C programs should be indented six feet downward and covered with dirt." -- Blair P. Houghton

4 7

Re: [Haskell] Trying to get a Composite design pattern to work
by Jared Updike 15 Mar '06

15 Mar '06

(Moved to haskell-cafe) > Actually, I'm trying to avoid library functions, so I can learn the > language and the functional way of thinking. How would one implement > the concatMap function? The Haskell 98 report gives possible implementations of standard functions: http://haskell.org/onlinereport/standard-prelude.html e.g. foldr :: (a -> b -> b) -> b -> [a] -> b foldr f z [] = z foldr f z (x:xs) = f x (foldr f z xs) map :: (a -> b) -> [a] -> [b] map f [] = [] map f (x:xs) = f x : map f xs concat :: [[a]] -> [a] concat xss = foldr (++) [] xss concatMap :: (a -> [b]) -> [a] -> [b] concatMap f = concat . map f etc. The book Haskell School of Expression (by Paul Hudak) goes over using recursion as a control structure and then shows you how to replace your simple recursion patterns with library functions once you start to see these general patterns. As you start to understand the functional style of iterating over lists, you should begin to see when to use the library functions, and how it will save you time and be more simple and clear than using recursion directly for every function. If you want a place to start, I would challenge you to expand the concatMap definition above with the definitions of concat and map, and then plug in the definition of foldr and see if you can make your own concatMap function. Maybe that will help you understand things better. Hope that helps, Jared. -- http://www.updike.org/~jared/ reverse ")-:"

4 4

Tree with collections
by Henning Thielemann 13 Mar '06

13 Mar '06

I have a problem with defining an instance. > module CollTree where > import Data.List(intersperse) Say, I want to define a tree structure based on lists. I omit the data attached to the nodes here for simplicity. > data ListTree = ListNode [ListTree] > deriving Show This is simple enough for an automatically derived Show instance. Now I want to generalise that structure from lists to arbitrary types of collections. > data CollTree coll = CollNode (coll (CollTree coll)) This got too complicated for automatic derivation. So I have to define a Show instance for CollTree manually. But how to formulate the instance context? How to avoid undecidable instances? instance ??? => Show (CollTree coll) where show (CollNode xs) = "CollNode " ++ show xs Currently I see only one solution using a new class providing a special 'show' routine, which handles the structure of the collection, but must be assisted by a custom 'show' function for the collection members. > class CollShow coll where > collShow :: (a -> String) -> (coll a -> String) > instance CollShow coll => Show (CollTree coll) where > show (CollNode xs) = "CollNode " ++ collShow show xs Now I have to write 'show' related code for each collection type. This way I probably duplicate a lot of code that is already written for the Show instances of the collections. To be honest, I use a more special tree structure with even more special "collections" so this may be not really a problem. Here an instance for a custom list type: > newtype NewList a = NewList [a] > instance CollShow NewList where > collShow shw (NewList xs) = > "(NewList [" ++ > concat (intersperse ", " (map shw xs)) ++ "])" Is there a more straightforward way, preferrably Haskell98?

2 2

Re: UArray
by Bulat Ziganshin 12 Mar '06

12 Mar '06

Hello Frederik, Sunday, March 12, 2006, 9:39:13 PM, you wrote: FE> Why define separate instances when one could just define one FE> equivalent one: FE> instance (Ix ix, Eq e, IArray UArray e) => Eq (UArray ix e) FE> (==) = eqUArray FE> ??? afaik, this is just not H98-compatible and require to use even more type extensions than currently used in this module FE> The same question applies to the Ord instances in that file. FE> I can give an answer *why not* do this: it makes UArray even more FE> unusable. UArrays which are polymorphic in their element types cannot FE> be compared. Here is another patch, please apply: _I_ don't apply the patches, but you can propose patches by sending them to libs maillist. tomorrow Simon Marlow will read it and decide whether it need to be applied most UArrays users don't need polymorphism, i run into problems with arrays only when i wrote general library which should support every array type -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

1 0