- Beginners - Haskell.org

pattern for tree traversel with a state
by Andreas-Christoph Bernstein 25 Oct '08

25 Oct '08

Hi, Is there a pattern for tree traversal with a state ? I am developing a small scenegraph represented by a tree. To draw a scenegraph one traverses over the graph starting with a global state. Inner Nodes can overwrite the inherited state for their subtree (e.g. Transformations are accumulated). The accumulated state is then either used immediately to draw the geometry in the leaf nodes, or a secondary data structure is build. This secondary data structure (a list or a tree) can then be sorted for optimal drawing performance. So i want to do the second and create a list of all leaves with the accumulated global state. To illustrate my problem i appended some code. The idea similar applies to a scenegraph. So my Question is: Is there allready a pattern for traversal with a state ? > module Main > where produces: Fork (0,"a") (Fork (1,"a") (Leaf (2,"a")) (Leaf (1,"a"))) (Leaf (0,"a")) > newTree :: BTree State > newTree = traverse modState globalState sampleTree produces: [(0,"a"),(1,"a"),(2,"a"),(1,"a"),(0,"a")] > stateList = flattenTree newTree > flattenTree (Leaf x) = [x] > flattenTree (Fork x l r) = [x] ++ flattenTree l ++ flattenTree r > type State = (Int, String) > > globalState :: State > globalState = (0, "a") State modifiers > data StateMod > = ModInt > | ModString > | ModNop > deriving Show > modState :: StateMod -> State -> State > modState ModInt (x,w) = (x+1,w) > modState ModNop s = s > modState ModString (x,w) = (x,'b':w) > data BTree a = Fork a (BTree a) (BTree a) > | Leaf a > deriving Show traverses the tree and executes a function which modifies the current state depending on the statemodifier > traverse :: (a -> b -> b) -> b -> BTree a -> BTree b > traverse f state (Leaf x) = Leaf (f x state) > traverse f state (Fork x l r) = > Fork (f x state) newLeft newRight > where newLeft = traverse f (f x state) l > newRight = traverse f (f x state) r an example tree > sampleTree :: BTree StateMod > sampleTree = Fork ModNop > (Fork ModInt (Leaf ModInt) (Leaf ModNop)) > (Leaf ModNop) creates a list from a tree > flattenTree (Leaf x) = [x] > flattenTree (Fork x l r) = [x] ++ flattenTree l ++ flattenTree r Thanks for any help and ideas Andreas

5 7

Type problems with IOArray
by Xuan Luo 24 Oct '08

24 Oct '08

I am having lots of trouble using polymorphic mutable IOArrays. Here is an example program: import Data.Array.MArray import Data.Array.IO foo x = do a <- newArray (0, 4) x readArray a 2 main = foo 42 >>= print So there is a function "foo" which makes an array of polymorphic type initialized with a value, then returns one of the elements of the array. So here "foo x" essentially does the same as "return x"; but it demonstrates problems I am having. So the above program fails with: testarray.hs:7:7: No instance for (MArray a t IO) arising from a use of `foo' at testarray.hs:7:7-12 Possible fix: add an instance declaration for (MArray a t IO) In the first argument of `(>>=)', namely `foo 42' In the expression: foo 42 >>= print In the definition of `main': main = foo 42 >>= print Okay; so the problem is that "newArray" is a function that creates MArrays in general; but there is no function to specifically create IOArrays in particular, and it doesn't know I want to use IOArrays. In fact, all the other functions that are used to operate on mutable arrays are generic MArray functions too, and there is basically nothing that is specific to IOArrays, so it is not as if the compiler can "figure it out from context". This is bad design. I wish it could just decide to default to IOArrays or something, since IOArrays of any type already are instances of MArray, so it would be natural. Okay so the general way to resolve this is to add signatures to tell it that it is an IOArray. But when I give the type for IOArray I also have to tell it what type its contents are, and I want it to work polymorphically over any type, so the array has to be of a polymorphic type: foo x = do a <- newArray (0, 4) x :: IO (IOArray Int a) readArray a 2 But of course it doesn't know what "a" is, so maybe I am forced to also add a signature for the function "foo" itself, which the compiler should really be able to figure out for me: import Data.Array.MArray import Data.Array.IO foo :: a -> IO a foo x = do a <- newArray (0, 4) x :: IO (IOArray Int a) readArray a 2 main = foo 42 >>= print Okay, now the real problems begin: testarray.hs:5:32: Couldn't match expected type `a1' against inferred type `a' `a1' is a rigid type variable bound by the polymorphic type `forall a1. IO (IOArray Int a1)' at testarray.hs:5:16 `a' is a rigid type variable bound by the type signature for `foo' at testarray.hs:4:7 In the second argument of `newArray', namely `x' In a 'do' expression: a <- newArray (0, 4) x :: IO (IOArray Int a) In the expression: do a <- newArray (0, 4) x :: IO (IOArray Int a) readArray a 2 What the heck is this? I looked through a lot of stuff online and eventually found that this works: {-# LANGUAGE ScopedTypeVariables #-} import Data.Array.MArray import Data.Array.IO foo :: forall a. a -> IO a foo x = do a <- newArray (0, 4) x :: IO (IOArray Int a) readArray a 2 main = foo 42 >>= print So I had to add some weird "forall" stuff to my function signature and enable some language extension flag(?). This seems way too complicated. I just want to be able to make and use a simple polymorphic array in the IO monad with regular Haskell, without changing compiler flags or anything like that. I have been doing well in other stuff involving the IO monad, but these mutable arrays really got me stuck. Thanks,

3 2

A Pascal-like Language Compiler
by Pranesh Srinivasan 23 Oct '08

23 Oct '08

Hi all, I have been learning haskell for the last month or so. I have just started becoming familiar with monads and looking at Parsec. As part of the Language Translators Course this semester, in the university I study, we are to implement a Pascal-like toy language to C translator[1]. The aim is to take a simple subset of Pascal and translate it to an intermediate 3 operand format, before translating it to simple C. The time I have for this project is about a month. I am contemplating doing this in Haskell, since I have read in several places that Haskell (and other functional languages) is very good for writing compilers. In fact, I have started writing code for lexing the basic tokens. I do have doubts about my ability to finish it. The curiosity to do something of a moderate size in Haskell, and the extremely friendly folks on #haskell, tipped me on this decision. I looked around for similar things on the internet, in vain. I have several doubts at this stage some of which include, * how the parser will determine the scope of the variables, i.e, how can a symbol table be implemented (in the state of the parser ?) * how easy or difficult will basic code optimisation (like unused variables, and loops with no side effects) and type checking be? * how would one go about implementing basic error recovery in the parser (make it skip the current line, or block) ? I would love it if I get a few pointers from people who have been there, done that. Or am I being too ambitious too early? :) [1] One of the suggested programming exercises at the end of the "Dragon" Compilers book, by Aho, et al. -- Pranesh S

3 5

how to define a user datatype consisting of instances of String?
by Benjamin L.Russell 23 Oct '08

23 Oct '08

How is it possible to define a user datatype consisting of instances of String? Suppose I am preparing a party for wine connoisseurs, and want to define the following data types: data Wine = Red | White data Red = "Merlot" data White = "Sauvignon Blanc" data Entree = "pork" | "chicken" | "tuna" data SideDish = "garlic bread" | "mozzarella sticks" | "caviar" Then, I want to write a Haskell function that takes two lists; e.g., ["pork", "chicken", "tuna"] and ["garlic bread", "mozzarella sticks", "caviar"] and that constructs a three-tuple of the following type: (Entree, SideDish, Wine) such that which Wine is chosen depends on the particular combination of Entree and SideDish, with respect to the following rules: ("pork", "garlic bread") -> ("pork", "garlic bread", "Merlot") ("pork", "mozzarella sticks") -> ("pork", "mozzarella sticks", "Merlot") ("pork", "caviar") -> ("pork", "Beluga", "Sauvignon Blanc") ("chicken", "garlic bread") -> ("chicken", "garlic bread", "Merlot") ("chicken", "mozzarella sticks") -> ("chicken", "mozzarella sticks", "Sauvignon Blanc") ("chicken", "caviar") -> ("chicken", "caviar", "Merlot") ("tuna", "garlic bread") -> ("tuna", "garlic bread", "Sauvignon Blanc") ("tuna", "mozzarella sticks") -> ("tuna", "mozzarella sticks", "Merlot") ("tuna", "caviar") -> ("tuna", "caviar", "Merlot") So far, I have written the following Haskell code: module Wine where data Wine = Red | White data Red = "Merlot" data White = "Sauvignon Blanc" data Entree = "pork" | "chicken" | "tuna" data SideDish = "garlic bread" | "mozzarella sticks" | "caviar" wine :: [Entree] -> [SideDish] -> [(Entree, SideDish, Wine)] wine entree sidedish | entree == "pork" = | sidedish == "garlic bread" = ("pork", "garlic bread", "Merlot") | sidedish == "mozzarella sticks" = ("pork", "mozzarella sticks", "Merlot") | sidedish == "caviar" = ("pork", "caviar", "Sauvignon Blanc") | entree == "chicken" = | sidedish == "garlic bread" = ("chicken", "garlic bread", "Merlot") | sidedish == "mozzarella sticks" = ("chicken", "mozzarella sticks", "Sauvignon Blanc") | sidedish == "caviar"= ("chicken", "caviar", "Merlot") | entree == "tuna" = | sidedish == "garlic bread" = ("tuna", "garlic bread", "Sauvignon Blanc") | sidedish == "mozzarella sticks" = ("tuna", "mozzarella sticks", "Merlot") | sidedish == "caviar"= ("tuna", "caviar", "Merlot") However, when I load this code into GHCi, I get the following error message: [1 of 1] Compiling Wine ( wine.hs, interpreted ) wine.hs:18:11: parse error on input `"' Failed, modules loaded: none. Prelude> I discovered the following seemingly relevant HaskellWiki page, but am not sure about how to apply the advice in it to this problem, because the advice does not seem sufficiently specific or detailed: List instance - HaskellWiki http://www.haskell.org/haskellwiki/List_instance What would be a good way to overcome this error? -- Benjamin L. Russell

2 11

what type is 'Val 9' when 'Val Int' a ctor for 'Expr e'?
by Larry Evans 23 Oct '08

23 Oct '08

The attachment compiles OK; yet, I don't understand how the compiler knows what type val_9 has. The compile/run is: <---cut here--- Compilation started at Tue Oct 21 13:17:41 make runghc uniplate.try.hs val_9=Val 9 add_8_9=Add (Val 8) (Val 9) children_add_8_9=[Val 8,Val 9] Compilation finished at Tue Oct 21 13:17:42 >---cut here--- I would have expected that I would need to code this: let val_9 = (Val 9)::(Expr Eo) but apparently not. Could somebody explain? TIA. -Larry

4 5

Re: [Haskell-beginners] do not understand Semantics of Case Expressions in report
by John Dorsey 21 Oct '08

21 Oct '08

Michael, (Sorry for duplicates; I sent this from the wrong address initially.) > (m) case v of { K { f1 = p1 , f2 = p2 , ... } -> e ; _ -> e' } > = case e' of { > y -> > case v of { > K { f1 = p1 } -> > case v of { K { f2 = p2 , ... } -> e ; _ -> y }; > _ -> y }} > where f1, f2, ... are fields of constructor K; y is a new variable [...] > I'm totally confused with this identity. Especialy with " = case e'". > Can anyone explain a little what does this rule stand, please? > It is better to see some example. You got me curious, so I looked over this. The table you reference lists identities that should hold for all implementations of case expressions. (m) is about how case matches against constructors with named fields, and it shows that a case expression that matches against multiple fields (f1, f2, etc.) can be broken into nested case expressions which each match a single field (eg. f1). It looks like "case e' of { y -> ..." was introduced solely to give e' a name that can be used in two places, since the nested form may fail to match at each level. It seems to me that without this, you could get code explosion from duplicating the expression e' below; with this you get sharing. Here it is with a interim step added: -- Match v against a constructor with multiple fields case v of { K { f1 = p1 , f2 = p2 , ... } -> e ; _ -> e' } -- Same, but introduce y to represent e' without loss of sharing case e' of { y -> case v of { K { f1 = p1 , f2 = p2 , ... } -> e ; _ -> y }} -- Same, but match first field of K independent of the rest case e' of { y -> case v of { K { f1 = p1 } -> case v of { K { f2 = p2 , ... } -> e ; _ -> y }; _ -> y }} I hope this helps. Regards, John

2 1

Weird compilation error while doing Euler problems?
by Ian Duncan 20 Oct '08

20 Oct '08

'm trying to compile my file that has my Euler problems in it to output the solution to problem four, but I'm getting a compile error. Here's my .hs file: ------------------------- module Euler1 where import Data.List import Data.Ord main = mapM_ putStrLn problem4 problem1 = foldl1' (+) $ nub $ (takeWhile (< 1000) [3,6..] ++ takeWhile (< 1000) [5,10..]) problem2 = sum $ takeWhile (<= 4000000) [x | x <- fibs, even x] where fibs = unfoldr (\(a,b) -> Just (a,(b,a+b))) (0,1) problem3 z = maximumBy compare (filter (\x -> z `mod` x == 0) (takeWhile (<= ceiling (sqrt (fromIntegral z))) primes)) problem4 = nub [ show $ y * z | y <- [100..999], z <- [100..999], show (y*z) == reverse (show $ y*z)] prime p = p `elem` primes primes = small ++ large where 1:p:candidates = roll $ mkWheel small small = [2,3,5,7] large = p : filter isPrime candidates isPrime n = all (not . divides n) $ takeWhile (\p -> p*p <= n) large divides n p = n `mod` p == 0 mkWheel ds = foldl nextSize w0 ds nextSize (Wheel n rs) p = Wheel (p*n) [r' | k <- [0..(p-1)], r <- rs, let r' = n*k+r, r' `mod` p /= 0] w0 = Wheel 1 [1] roll (Wheel n rs) = [n*k+r | k <- [0..], r <- rs] data Wheel = Wheel Integer [Integer] ------------------------ Here's my output when I try to compile: ian$ ghc ~/Documents/eulerProblem1.hs -o test Undefined symbols: "___stginit_ZCMain", referenced from: ___stginit_ZCMain$non_lazy_ptr in libHSrts.a(Main.o) "_ZCMain_main_closure", referenced from: _ZCMain_main_closure$non_lazy_ptr in libHSrts.a(Main.o) ld: symbol(s) not found collect2: ld returned 1 exit status What's going on? I'm running GHC 6.8.3, if that helps.

3 2

do not understand Semantics of Case Expressions in report
by Michael Mekhanoshin 20 Oct '08

20 Oct '08

at http://www.haskell.org/onlinereport/exps.html on figure Figure 4 (Semantics of Case Expressions, Part 2) one can see: (m) case v of { K { f1 = p1 , f2 = p2 , ... } -> e ; _ - > e' } = case e' of { y -> case v of { K { f1 = p1 } -> case v of { K { f2 = p2 , ... } -> e ; _ -> y }; _ -> y }} where f1, f2, ... are fields of constructor K; y is a new variable (In Figures 3.1--3.2: e, e' and ei are expressions; g and gi are boolean-valued expressions; p and pi are patterns; v, x, and xi are variables; K and K' are algebraic datatype (data) constructors (including tuple constructors); and N is a newtype constructor.) I'm totally confused with this identity. Especialy with " = case e'". Can anyone explain a little what does this rule stand, please? It is better to see some example. Respect, Michael

1 0

Re: [Haskell-beginners] requested module name differs from name found in interface file
by Larry Evans 20 Oct '08

20 Oct '08

On 10/20/08 11:38, Justin Bailey wrote: > On Mon, Oct 20, 2008 at 9:25 AM, Larry Evans <cppljevans(a)suddenlink.net> wrote: > [snip] > >> Do you mean install it manually as shown in the aforementioned >> How_to_install_a_Cabal_package? >> > > No, I mean go to http://hackage.haskell.org and download the .tar.gz > file directly (http://hackage.haskell.org/cgi-bin/hackage-scripts/package/category-extras) > Unzip/untar that package. I haven't looked at it, but there is > probably a "src" directory. Put your example file in there and load it > in ghci. Your source file should then use the source available in that > directory tree rather than the category-extras install which seems > broken. This works because the GHC will look at the import > "Control.Functor.Fix" and use that to look for > "Control/Functor/Fix.hs" from the current directory. > Tried that but: <--- cut here --- GHCi, version 6.8.2: http://www.haskell.org/ghc/ :? for help Loading package base ... linking ... done. Prelude> :load "/home/evansl/download/haskell/libs/category-extras-0.53.5/src/catamorphism.example.hs" Control/Category/Dual.hs:17:7: Could not find module `Control.Category': Use -v to see a list of the files searched for. Failed, modules loaded: none. Prelude> <--- cut here --- If it's any help, the directory list for src/Control/Category is: <--- cut here --- /home/evansl/download/haskell/libs/category-extras-0.53.5/src/Control/Category: total used in directory 52 available 148798604 drwxr-xr-x 3 evansl evansl 4096 Jun 30 08:08 . drwxr-xr-x 9 evansl evansl 4096 Jun 30 08:08 .. -rw-r--r-- 1 evansl evansl 2118 Jun 30 08:08 Associative.hs -rw-r--r-- 1 evansl evansl 1668 Jun 30 08:08 Braided.hs drwxr-xr-x 2 evansl evansl 4096 Jun 30 08:08 Cartesian -rw-r--r-- 1 evansl evansl 4973 Jun 30 08:08 Cartesian.hs -rw-r--r-- 1 evansl evansl 1020 Jun 30 08:08 Discrete.hs -rw-r--r-- 1 evansl evansl 1340 Jun 30 08:08 Distributive.hs -rw-r--r-- 1 evansl evansl 668 Jun 30 08:08 Dual.hs -rw-r--r-- 1 evansl evansl 578 Jun 30 08:08 Hask.hs -rw-r--r-- 1 evansl evansl 3254 Jun 30 08:08 Monoidal.hs -rw-r--r-- 1 evansl evansl 1746 Jun 30 08:08 Object.hs >--- cut here --- > You might have more luck finding out what's going on by emailing > Haskell-Cafe directly, too. > Yes, thanks. > Justin > >

1 0

requested module name differs from name found in interface file
by Larry Evans 19 Oct '08

19 Oct '08

With a file containing: > module Main where > > import Array > import Control.Functor.Fix I get: > make > ghc -i/root/.cabal/lib/category-extras-0.53.5/ghc-6.8.2 -c > catamorphism.example.hs > > catamorphism.example.hs:19:0: > Bad interface file: > /root/.cabal/lib/category-extras-0.53.5/ghc-6.8.2/Control/Functor/Fix.hi > Something is amiss; requested module main:Control.Functor.Fix > differs from name found in the interface file > category-extras-0.53.5:Control.Functor.Fix > make: *** [all] Error 1 I used cabal to install category-extras: > /home/evansl/download/haskell/libs # cabal install category-extras > Resolving dependencies... > Downloading category-extras-0.53.5... > Configuring category-extras-0.53.5... > Preprocessing library category-extras-0.53.5... ... > /usr/bin/ar: creating dist/build/libHScategory-extras-0.53.5.a > Installing library in /root/.cabal/lib/category-extras-0.53.5/ghc-6.8.2 > Registering category-extras-0.53.5... > Reading package info from "dist/installed-pkg-config" ... done. > Saving old package config file... done. > Writing new package config file... done. > /home/evansl/download/haskell/libs # What should I do to import the Functor.Fix as shown here: http://comonad.com/reader/2008/recursion-schemes/ TIA. -Larry

1 0