- Haskell-Cafe - Haskell.org

Class
by Slavomir Kaslev 02 Nov '06

02 Nov '06

Hello. I am new to Haskell and I am going through "Haskell: The craft of functional programming". I am trying to grasp haskell's classes and instances, so here is slightly modified code from the book: class Show a => Visible a where toString :: a -> String toString = show size :: a -> Int size = length . show instance Visible a => Visible [a] where toString = concat . map toString size = foldl (+) 0 . map size vSort :: (Visible a, Ord a) => [a] -> String vSort = toString . List.sort s = vSort [1..3] Unfortunetly in ghc it gives the following type error: Ambiguous type variable `a' in the constraints: `Visible a' arising from use of `vSort' at d:/tmp.hs:83:4-8 `Enum a' arising from the arithmetic sequence `1 .. 3' at d:/tmp.hs:83:10-15 `Num a' arising from the literal `3' at d:/tmp.hs:83:14 `Ord a' arising from use of `vSort' at d:/tmp.hs:83:4-8 Probable fix: add a type signature that fixes these type variable(s) Failed, modules loaded: none. As you can see, Visible is nothing more than an adapter to the Show class. How I got thing so far, [1..3] :: (Num a, Enum a) => [a], has a Show instance so does class Num (which 'subclasses' Show). Therefore, I can't see any reason why toString function can't call show from those instances. Can someone please enlighten my (still) C++ thinking head? -- Slavomir Kaslev

3 3

Basic Binary IO
by Nuno Pinto 02 Nov '06

02 Nov '06

Hi all! Today i was reading System.IO and didn't manage to understand how it works just by reading it. I looked the internet for some help on this, but only "advanced" information is available. Can anyone show me how to use openBinaryFile ? Just an example, like opening file "somefile" and separating it into something that can be edited in the code (like 8 bit words) then go to word nr12 and edit the last bit? Thanks! NP _________________________________________________________________ Search from any Web page with powerful protection. Get the FREE Windows Live Toolbar Today! http://www.toolbar.live.com

3 2

Re: [Haskell-cafe] What is the best way to preserve the order of a list (RESOLVED)
by John Ky 02 Nov '06

02 Nov '06

Thanks Stefan, -John On 11/1/06, Stefan Holdermans <stefan(a)cs.uu.nl> wrote: > > John, > > > 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. > > Straightforwardly, you could do it like this: > > import List (sortBy) > > type Priority = Int > type Order = Int > > order :: [Priority] -> [(Priority, Order)] > order = unlabel . sortOnLab . assignOrder . sortOnPrio . label > where > label = zip [0 ..] > unlabel = map snd > sortOnLab = sortBy (\(l, _) (m, _) -> compare l m) > sortOnPrio = sortBy (\(_, p) (_, q) -> compare p q) > assignOrder = \xs -> zipWith (\(l, p) o -> (l, (p, o))) xs [0 ..] > > For instance: > > > order [5, 2, 3, 7] > [(5,2),(2,0),(3,1),(7,3)] > > HTH, > > Stefan >

1 0

Post mesg
by Farida Mishra 02 Nov '06

02 Nov '06

Hi i would like to post mesg this list --------------------------------- Everyone is raving about the all-new Yahoo! Mail.

2 1

there's a monster in my Haskell!
by Andrew Pimlott 01 Nov '06

01 Nov '06

To boost the popularity of Scheme, Felleisen has argued for renaming "lambda" to "something cool, such as Funster".[1] Likewise, Haskell intimidates newcomers with the arcane term "monad". Peyton Jones's hopeful campaign to replace it with "warm fuzzy thing"[2] has so far produced few results. Inspired by Felleisen, and in the spirit of Halloween, I offer a new alternative: Meet "monsters", your computational companions in the land of lazy functional programming. To illustrate this proposal, I present here a gentle introduction to monsters. Monsters come in great variety, each type having its own special powers. But, as noted by Elmo[3], they are alike in an essential way. All monsters are capable of devouring values: devour :: Monster m => a -> m a The result of "devour x" is simply a monster that has ingested the value "x". Most monsters have a weakness and can be slain, liberating some ingested values or producing some other result. The instrument of demise varies, as do the possible outcomes, so this function is particular to a monster. If SomeMonster always yields a single value upon its demise, we would have slay :: SomeMonster a -> a The compassionate (and fastidious) programmer defers the gruesome (and messy) slaying while making use of the monster's special powers. But how to get at the monster's values short of that macabre act? Fortunately, monsters gladly contribute their values towards the creation of more monsters: (>>=) :: Monster m => m a -> (a -> m b) -> m b (>>=) should be read as the monster on the left expelling values through its rows of teeth and over its tongue at the function on the right. (Its pronunciation is a sort of bestial hissing that is difficult to describe; when you say it correctly, the terminal may become slightly moist.) Monsters range from the tame to the tumultuous, but we cannot let them run entirely amok. All therefore must obey the "monster laws". For instance, the regurgitation law states that immediately after devouring a value, a monster expels the same value: devour x >>= k === k x We have still seen none of the promised special powers. For that, we must look at a particular monster. The Either monster is defined as data Either a b = Trick a | Treat b This monster devours Treats, but if it doesn't get a Treat, it can play a Trick: playTrick :: t -> Trick t a playTrick t = Trick t This monster is commonly used as follows: takeFood :: Food -> Either Mischief Food takeFood Apple = playTrick eggHouse takeFood Raisins = playTrick tpTree takeFood CandyCorn = devour CandyCorn The divine among monsters is the mysterious and awesome IO. Its powers are vast, perhaps limitless, and beginners are taught that it cannot be slain. Like poisoned candy and release dates, this is of course a myth. The pure of spirit may, after meditation at the altar of referential transparency, cast the spell :: IO a -> a (When you are prepared to call this function, its name will be revealed.) The ST monster can be slain without esoteric ritual: slay :: (forall s. ST s a) -> a Yet philosophers whisper that there is something otherworldly about it, a kinship with IO. Eavesdropping on their debates, I hear the words "phantom type", but that gives me the chills so I leave them. [1] http://permalink.gmane.org/gmane.comp.lang.lightweight/3427 [2] http://research.microsoft.com/~simonpj/papers/haskell-retrospective/ [3] http://muppet.wikia.com/wiki/We%27re_All_Monsters

6 5

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