- Haskell-Cafe - Haskell.org

What is the best way to preserve the order of a list
by John Ky 01 Nov '06

01 Nov '06

Hi, I have a list of entities. Each entity has a priority field and an order field. The priority field contain the input values to my algorithm, the order fields contain the output value of my algorithm. My algorithm needs to assign 1 to the order field of the entity with the lowest priority value, 2 to the order field of the entity with the next lowest priority value, .... and so on. I've written a function orderByPriority that does that. However, it also does something else that is undesireable. It reorders the list. My question is, how do I preserve the ordering of entities in my list and still be able to assign the proper order values to each entity? Is there an efficient way to do this? How else might I improve my orderByPriority algorithm. Thanks -John > import Data.List > data Entity = Entity { > entityId :: Int, > priority :: Float, > order :: Int > } > initEntity = Entity { > entityId = 0, > priority = 0.0, > order = 0 > } > myList = [ > initEntity { entityId = 1, priority = 8.7 }, > initEntity { entityId = 2, priority = 5.4 }, > initEntity { entityId = 3, priority = 2.9 }, > initEntity { entityId = 4, priority = 5.4 }, > initEntity { entityId = 5, priority = 1.3 }, > initEntity { entityId = 6, priority = 3.5 }, > initEntity { entityId = 7, priority = 9.5 } > ] > comparePriority entity1 entity2 = > compare (priority entity1) (priority entity2) > orderByPriority :: [Entity] -> [Entity] > orderByPriority entities = assignOrder orderList 1 > where > orderList = sortBy comparePriority entities > assignOrder [] _ = [] > assignOrder (entity:entities) count = > (entity { order = count }):(assignOrder entities (count + 1)) > instance Show Entity where > show entity = "{" ++ > "entityId:" ++ (show $ entityId entity) ++ "," ++ > "priority:" ++ (show $ priority entity) ++ "," ++ > "order: " ++ (show $ order entity) ++ > "}"

4 4

class Defaults
by Bulat Ziganshin 01 Nov '06

01 Nov '06

Hello haskell-cafe, just one more nice snippet of code: class Defaults a where defaultValue :: a instance Defaults Bool where defaultValue = False instance Defaults [a] where defaultValue = [] instance Defaults (a->a) where defaultValue = id instance Num a => Defaults a where defaultValue = 0 class TestDefaultValue a where isDefaultValue :: a -> Bool instance TestDefaultValue Bool where isDefaultValue = not instance TestDefaultValue [a] where isDefaultValue = null instance Num a => TestDefaultValue a where isDefaultValue = (==0) -- This function is useful for defining default values, -- such as (directory ||| ".") or (memsize ||| 10*mb) a ||| b | isDefaultValue a = b | otherwise = a -- Useful for short-cutting boolean expressions, like this: -- putStr$ (need_separator &&& "\n\n") ++ (need_attention &&& map toUpper) str a &&& b | isDefaultValue a = defaultValue | otherwise = b -- |Apply function to value only if it is not empty unlessNull f xs = xs &&& f xs -- |Recursive list processing until list end, -- for example 'recursive (splitAt n)' splits list -- into the chuunks of n elements recursive :: ([a]->(b,[a])) -> [a] -> [b] recursive f list = list &&& (x:recursive f xs) where (x,xs) = f list -- |Split list into parts whose size defined by calling len_f -- at the yet unprocessed parts of list splitByLen :: ([a]->Int) -> [a] -> [[a]] splitByLen len_f = recursive (\xs -> splitAt (len_f xs) xs) -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

1 0

Simple GADT parser for the eval example
by Greg Buchholz 01 Nov '06

01 Nov '06

I'm trying to create a simple parser for the GADT evaluator from the wobbly types paper, and I need a little help. Here's the GADT and the evaluator... > data Term a where > Lit :: Int -> Term Int > Inc :: Term Int -> Term Int > IsZ :: Term Int -> Term Bool > If :: Term Bool -> Term a -> Term a -> Term a > Pair :: Term a -> Term b -> Term (a,b) > Fst :: Term (a,b) -> Term a > Snd :: Term (a,b) -> Term b > > eval :: Term a -> a > eval (Lit i) = i > eval (Inc t) = eval t + 1 > eval (IsZ t) = eval t == 0 > eval (If b t e) = if eval b then eval t else eval e > eval (Pair a b) = (eval a, eval b) > eval (Fst t) = fst (eval t) > eval (Snd t) = snd (eval t) > ...and instead of writing my own read instance, I thought I'd take a shortcut and just try converting a regular data type to our generalized one... > data Expr = ELit Int > | EInc Expr > | EIsZ Expr > | EPair Expr Expr > | EIf Expr Expr Expr > | EFst Expr > | ESnd Expr > deriving (Read,Show) > > my_read' :: Expr -> Term a > my_read' (ELit a) = Lit a > my_read' (EInc a) = Inc (my_read' a) > my_read' (EIsZ a) = IsZ (my_read' a) > my_read' (EPair a b) = Pair (my_read' a) (my_read' b) > my_read' (EIf p t e) = If (my_read' p) (my_read' t) (my_read' e) > my_read' (EFst a) = Fst (my_read' a) > my_read' (ESnd a) = Snd (my_read' a) ...That looks nice and simple, but it doesn't type check. GHCi-6.6 complains... Couldn't match expected type `a' (a rigid variable) against inferred type `Int' `a' is bound by the type signature for `my_read' at eval_gadt_wobbly.hs:45:24 Expected type: Term a Inferred type: Term Int In the expression: Lit a In the definition of `my_read': my_read (ELit a) = Lit a ...No surprise there, since there is no way to fail in the event of a maltyped "Expr". The next thing to try is a type class solution... > class MyRead a where > my_read :: Expr -> Term a > > instance MyRead Int where > my_read (ELit a) = Lit a > my_read (EInc a) = Inc (my_read a) > my_read (EIf p t e) = If (my_read p) (my_read t) (my_read e) > my_read (EFst a) = Fst (my_read a :: MyRead b => Term (Int,b)) > -- my_read (ESnd a) = Snd (my_read a) > instance MyRead Bool where > my_read (EIsZ a) = IsZ (my_read a) > my_read (EIf p t e) = If (my_read p) (my_read t) (my_read e) > -- my_read (EFst a) = Fst (my_read a) > -- my_read (ESnd a) = Snd (my_read a) > instance (MyRead a, MyRead b) => MyRead (a,b) where > my_read (EPair a b) = Pair (my_read a) (my_read b) > my_read (EIf p t e) = If (my_read p) (my_read t) (my_read e) > -- my_read (EFst a) = Fst (my_read a) > -- my_read (ESnd a) = Snd (my_read a) This just about works, except for the definitions for the "Fst" and "Snd" constructors. The compiler complains... Ambiguous type variable `b' in the constraint: `MyRead b' arising from use of `my_read' at eval_gadt_wobbly.hs:65:28-36 Probable fix: add a type signature that fixes these type variable(s) ...Of course, that makes perfect sense, since, if we're applying "Fst" to a term, then we don't care about the other branch of the "Pair". You can get it accepted by the type checker by making the types more concrete... my_read (EFst a) = Fst (my_read a :: Term (Int,Int)) ...or... my_read (EFst a) = Fst (my_read a :: Term (Int,Bool)) ...but how does a person fix this to work in the more general case? Or is this even the right way to build a parser for the GADT evaluator example? Notice the repetition needed: the "If", "Fst", and "Snd" defintions have to be copied to all three instances. Also, feel free to comment on this example, and the fact that it will evaluate with no problems. > static_vs_laziness = eval (my_read (EIf (EIsZ (ELit 0)) > (ELit 9) > (EIsZ (ELit 42)))::Term Int) Thanks, Greg Buchholz

7 9

hmake and ghc-6.6
by Alexey Rodriguez 01 Nov '06

01 Nov '06

Hello Haskell people, I have been trying to build hmake 3.12 using ghc-6.6 on a Fedora Core Linux running on a dual 64-bit Opteron machine. However, I had the following error related to the readline library: ---- /home/t-alexer/packages/hmake-3.12/script/hmake -hc=ghc HInteractive -d/home/t-alexer/packages/hmake-3.12/targets/x86_64-Linux/obj/interpreter \ -i../hmake -package util -package base -DUSE_READLINE=1 -lreadline -lncurses Warning: package(s) util not available (according to ghc-pkg) MkProg: Can't find module Readline in user directories . ../hmake Or in installed libraries/packages at /home/simonmar/fp/lib/x86_64-unknown-linux/ghc-6.6/imports /home/simonmar/fp/lib/x86_64-unknown-linux/ghc-6.6/imports Asked for by: SimpleLineEditor.hs Fix using the -I, -P, or -package flags. Stop - hmake dependency error. ---- I googled for this error and I saw the following thread in which Malcolm suggested having a fix. http://www.nabble.com/hmake-and-GHC-6.6-t2531880.html I tried to locate hmake's repository but to no avail. There is no link to it from www.haskell.org/hmake and the hmake in the nhc repository is the same as the hmake I downloaded. I will appreciate any help you can offer. Cheers, Alexey P.S. A related question, has any of you tried to build ghc using hat? I am trying to do this to study ghc's internals

2 2

An example of dependent types [was: Simple GADT parser for the eval example]
by oleg＠pobox.com 01 Nov '06

01 Nov '06

Greg Buchholz has posed an interesting problem of writing a typechecker. Given untyped terms of the form > data Expr = ELit Int > | EInc Expr > | EIsZ Expr .... we are to compute typed terms: > data Term a where > Lit :: Int -> Term Int > Inc :: Term Int -> Term Int > IsZ :: Term Int -> Term Bool That is, we need to write a function > typecheck :: Expr -> Term a Actually, Greg Buchholz posed a simpler example, of a function my_read > my_read :: Expr -> Term a Although it has the same signature, the intent is different. When the user writes "my_read exp", the user is supposed to *specify* the type of the desired result. Just as when we write "read 1", we are supposed to specify the type of the expected value: Int, Integer, etc. The function typecheck has a different intent: it *computes* the result type. It is indeed the typechecker: given the expression, we compute its type -- or report a failure if the expression is ill-typed. That is, the result *type* "Term a" is a function of the *value* Expr. Thus is truly a problem of dependent types. And Haskell is up to it: Haskell is genuinely a dependently typed language. We show the solution that uses no GADTs and no representation types. We retain however the eval function in the previous message that uses GADT. Our solution uses type classes. It seems to some the type-checking rules stated as instances of the TypeCheck class take a particular natural form. Indeed: > -- given term e, compute its type t > class TypeCheck e t | e -> t where > typecheck :: e -> Term t > instance TypeCheck FLit Int where > typecheck (FLit x) = Lit x > instance TypeCheck e Int => TypeCheck (FInc e) Int where > typecheck (FInc e) = Inc (typecheck e) > instance TypeCheck e Int => TypeCheck (FIsZ e) Bool where > typecheck (FIsZ e) = IsZ (typecheck e) > instance (TypeCheck e1 Bool, TypeCheck e2 t, TypeCheck e3 t) > => TypeCheck (FIf e1 e2 e3) t where > typecheck (FIf e1 e2 e3) = If (typecheck e1) (typecheck e2)(typecheck e3) > instance (TypeCheck e1 t1, TypeCheck e2 t2) > => TypeCheck (FPair e1 e2) (t1,t2) where > typecheck (FPair e1 e2) = Pair (typecheck e1) (typecheck e2) > instance TypeCheck e (t1,t2) => TypeCheck (FFst e) t1 where > typecheck (FFst e) = Fst (typecheck e) > instance TypeCheck e (t1,t2) => TypeCheck (FSnd e) t2 where > typecheck (FSnd e) = Snd (typecheck e) In the paper, the IsZ rule would have been written as |- e : int --------------- |- IsZ e : bool (We don't need the environment Gamma as our language has no variables). I submit the typeclass notation takes less space. The typechecking rules above operate on `lifted' terms: FLit, FInc, etc: > newtype FLit = FLit Int > newtype FInc e = FInc e > newtype FIsZ e = FIsZ e rather than the original terms Exp. The conversion is straightforward, via Template Haskell: > type F = Q TH.Exp > parse :: Expr -> F > parse (ELit x) = [e| FLit $(litE . integerL . fromIntegral $ x) |] > parse (EInc x) = [e| FInc $(parse x) |] > parse (EIsZ x) = [e| FIsZ $(parse x) |] The only inconvenience of using the Template Haskell is the necessity of splitting the whole code into two modules. we can then write: > e1 = "EIf (ELit 1) (ELit 2) (ELit 3)" > e2 = "(EIf (EIsZ (ELit 0)) " ++ > " (EInc (ELit 1)) " ++ > " (EFst (EPair (ELit 42) " ++ > " (ELit 43))))" > > t1' = $(parse . read $ e1) > t2' = $(parse . read $ e2) *G> :t t1' t1' :: FIf FLit FLit FLit *G> :t t2' t2' :: FIf (FIsZ FLit) (FInc FLit) (FFst (FPair FLit FLit)) > -- Causes the typechecking error: cannot match Int against the Bool > -- tt1 = typecheck t1' > tt2 = typecheck t2' *G> :t tt2 tt2 :: Term Int Obviously, e1 is ill-formed and so cannot be typechecked. The term e2 is well-typed, and the typechecker has figured out its type, which is Term Int. There was no need for any type annotation. The term tt2 can then be evaluated. The code: file GP.hs {-# OPTIONS -fglasgow-exts #-} module GP where import Language.Haskell.TH hiding (Exp) import qualified Language.Haskell.TH as TH (Exp) import Language.Haskell.TH.Ppr -- untyped terms, at Level 0 data Expr = ELit Int | EInc Expr | EIsZ Expr | EPair Expr Expr | EIf Expr Expr Expr | EFst Expr | ESnd Expr deriving (Read,Show) -- Untyped terms, at Level 1 type F = Q TH.Exp newtype FLit = FLit Int newtype FInc e = FInc e newtype FIsZ e = FIsZ e data FPair e1 e2 = FPair e1 e2 data FIf e1 e2 e3 = FIf e1 e2 e3 newtype FFst e = FFst e newtype FSnd e = FSnd e parse :: Expr -> F parse (ELit x) = [e| FLit $(litE . integerL . fromIntegral $ x) |] parse (EInc x) = [e| FInc $(parse x) |] parse (EIsZ x) = [e| FIsZ $(parse x) |] parse (EFst x) = [e| FFst $(parse x) |] parse (ESnd x) = [e| FSnd $(parse x) |] parse (EPair x y) = [e| FPair $(parse x) $(parse y) |] parse (EIf x y z) = [e| FIf $(parse x) $(parse y) $(parse z) |] show_code cde = runQ cde >>= putStrLn . pprint t0 = show_code . parse . read $ "EInc (EInc (ELit 1))" -- ill-typed expression e1 = "EIf (ELit 1) (ELit 2) (ELit 3)" e2 = "(EIf (EIsZ (ELit 0)) " ++ " (EInc (ELit 1)) " ++ " (EFst (EPair (ELit 42) " ++ " (ELit 43))))" t1 = show_code . parse . read $ e1 File g2.hs {-# OPTIONS -fglasgow-exts #-} {-# OPTIONS -fallow-undecidable-instances #-} module G where import GP -- Typed terms data Term a where Lit :: Int -> Term Int Inc :: Term Int -> Term Int IsZ :: Term Int -> Term Bool If :: Term Bool -> Term a -> Term a -> Term a Pair :: Term a -> Term b -> Term (a,b) Fst :: Term (a,b) -> Term a Snd :: Term (a,b) -> Term b -- Typed evaluator [elided] -- Figure out the type of the expression e -- The type-checking rules are written in the natural notation [see the TypeCheck class and instances above. Elided to save space] t0' = $(parse . read $ "EInc (EInc (ELit 1))") t1' = $(parse . read $ e1) t2' = $(parse . read $ e2) tt0 = typecheck t0' -- Causes the typechecking error: cannot match Int against the Bool -- tt1 = typecheck t1' tt2 = typecheck t2' ttt0 = eval tt0 ttt2 = eval tt2

2 1

function types as instances of Num
by Greg Buchholz 01 Nov '06

01 Nov '06

Let's say we've got a little stack language, where you compute things by transformations of stacks, using compositions of functions from stacks to stacks (represented here as nested tuples). (See also Chris Okasaki's "Techniques for Embedding Postfix Languages in Haskell" www.eecs.harvard.edu/~nr/ cs252r/archive/chris-okasaki/hw02.ps ) For example, the simple program below calculates the square of 4... > {-# OPTIONS -fglasgow-exts #-} > > main = print $ test () > > test = square . (lit 4) > > lit :: Integer -> a -> (Integer,a) > lit val stack = (val, stack) > > dup (a, b) = (a, (a, b)) > mult (a, (b, c)) = (b*a, c) > square = mult . dup ...now let's say I find that using the function "lit" to annotation numeric literals ugly. What I really want is something like... > test' = square . 4 ...Seems simple enough, I'll just make an appropriate instance of Num and I'll be able to use fromInteger... > instance Eq (a -> (Integer, a)) > instance Show (a -> (Integer, a)) > instance Num (a -> (Integer, a)) where > fromInteger = lit ...but now when I try it, GHC complains... No instance for (Num (a -> (Integer, t))) arising from the literal `4' at final.hs:15:17 Possible fix: add an instance declaration for (Num (a -> (Integer, t))) In the second argument of `(.)', namely `4' In the expression: square . 4 In the definition of `test'': test' = square . 4 ...so it seems that (a -> (Integer, t)) can't be unified with (a -> (Integer, a)), or somesuch. Any thoughts on how to get this to work? Thanks, Greg Buchholz

4 5

More documentation: how to create a Haskell project
by dons＠cse.unsw.edu.au 01 Nov '06

01 Nov '06

There's been a bit of discussion on irc, lists and privately about about documenting publically the best practice for creating a new Haskell project -- be that a library or an application. Some advice is now available here: http://haskell.org/haskellwiki/How_to_write_a_Haskell_program Suggestions include: * use darcs * use cabal But we could do with more information on: * where to host a haskell project * integration of testsuites * anything about Hackage? * portability issues? So have a look at the page and make some suggestions, so it will be easier for newcomers in the future to create and contribute new projects, that will be readily accesible, useable and adopted by the community. -- Don

8 7

Accumulating related XML nodes using HXT
by Daniel McAllansmith 31 Oct '06

31 Oct '06

Hello. I have some html from which I want to extract records. Each record is represented within a number of <tr> nodes, and all records <tr> nodes are contained by the same parent node. The things I've tried so far end up giving me the cartesian product of record fields, so for the html fragment included below I'd end up with: [ Prod "Television" 17 "/prod17" "A very nice telly." , Prod "Television" 17 "/prod17" "Mind your fillings." , Prod "Cyclotron" 24 "/prod24" "A very nice telly." , Prod "Cyclotron" 24 "/prod24" "Mind your fillings." ] instead of: [ Prod "Television" 17 "/prod17" "A very nice telly." , Prod "Cyclotron" 24 "/prod24" "Mind your fillings." ] How should I go about accumulating related <tr> nodes into individual records? Thanks Daniel HTML fragment follows: ... <tr> <tr> <td>Product:</td> <td><a href="/prod17">Television</a> (code: 17)</td> </tr> <tr> <td>Description:</td> <td>A very nice telly.</td> </tr> <tr> <td><hr color="#00000"></td> </tr> <tr> <td>Product:</td> <td><a href="/prod24">Cyclotron</a> (code: 24)</td> </tr> <tr> <td>Description:</td> <td>Mind your fillings.</td> </tr> <tr> <td><hr color="#00000"></td> </tr> </tr> ...

2 3

hdbc linking errors
by Jeff Polakow 31 Oct '06

31 Oct '06

Hello, When trying to compile a standalone program using hdbc in cygwin, I get many linker errors. I have no problems using my code interactively with ghci. I am using the command line: ghc --make -package HDBC -package HDBC-odbc -O -o testExecute testExecute.hs Am I missing something? thanks Jeff -- This e-mail may contain confidential and/or privileged information. If you are not the intended recipient (or have received this e-mail in error) please notify the sender immediately and destroy this e-mail. Any unauthorized copying, disclosure or distribution of the material in this e-mail is strictly forbidden.

1 1

Why is Haskell not homoiconic?
by Henning Sato von Rosen 31 Oct '06

31 Oct '06

Hi all! I am curious as to why Haskell not is homoiconic? I am interested in the reasons behind that design descision. I ask using this defintion og homiconicity: Homiconic means that "the primary representation of programs is also a data structure in a primitive type of the language itself" -- http://en.wikipedia.org/wiki/Homoiconic Examples: LISP, Rebol, Natural Languages... Thank you/Henning

4 3