January 2005 - Haskell-Cafe

Re: [Haskell-cafe] Guards (Was: Some random newbie questions)
by Jon Cast 10 Jan '05

10 Jan '05

Henning Thielemann <lemming(a)henning-thielemann.de> wrote: <snip> > What about dropping Guards? :-) Are they necessary? Do they lead to > more readable source code? Absolutely. In Haskell's syntax, if-then-else-if interacts badly with do notation, and Haskell lacks a direct analogy to Lisp's cond. case () of () | p1 -> e1 | p2 -> e2 ... works beautifully as a replacement. Also, GHC's pattern guards are a nice feature, and frequently seem clearer than case. Compare, e.g., parseCmd ln | Left err <- parse cmd "Commands" ln = BadCmd $ unwords $ lines $ show err | Right x <- parse cmd "Commands" ln = x with the Haskell-98 alternative parseCmd ln = case parse cmd "Commands" ln of Left err -> BadCmd $ unwords $ lines $ show err Right x -> x The trade-off: using pattern guards makes it harder to verify (and ensure) that the exact same expression is being matched against; using case makes it harder to see exactly what is being matched against. Furthermore, guards are an extension of pattern matching, which means you can write code like this: xn !! n | n < 0 = error "Prelude.(!!): Negative index" [] !! n = error "Prelude.(!!): Index overflow" (x:xn) !! n | n == 0 = x (x:xn) !! n = xn !! (n - 1) Exactly one equation for each edge in the control-flow graph, which is nice and not easily done (I'm not sure it's even possible) without guards. Pattern guards are also nice for implementing ‘views’: -- | Convert an 'XMLData' into an equivalent application of -- 'Balanced', if possible. In any case, return an equivalent data -- structure. balance (Balanced es) = Balanced es balance (LeftLeaning (LeftBalanced e:es)) | Balanced es' <- balance (LeftLeaning es) = Balanced (e:es') balance (LeftLeaning []) = Balanced [] balance (RightLeaning [("", "", es)]) = Balanced es balance (RightLeaning []) = Balanced [] balance e = e Where XMLData can store a (nearly) arbitrary fragment of an XML document. The problem being solved by the pattern guard in the second equation is that the data type is ambiguous; there is more than one way to represent a ‘balanced’ XML fragment (that is, the concatenation of a sequence of well-formed XML fragments and CDATA sections). This function attempts to coerce the data structure passed in into a canonical representation; it succeeds if the data is in fact balanced and fails otherwise. The pattern guard illustrates how to use this function as a replacement for pattern matching on Balanced, to catch all cases where the argument is in fact balanced (we can't use it in this case as a replacement for the first equation, since that create an infinite loop, but in other functions we could). I'm sure there are uses I'm forgetting, but I think that's enough. > Do they lead to more efficient code? I could perfectly live without > them up to now. Well, I could never do without them. Jonathan Cast

3 2

RE: [Haskell-cafe] RE: Enum class
by Arjun Guha 09 Jan '05

09 Jan '05

Sorry, that was a stupid error. I meant to use fromEnum: > next:: (Enum a, Bounded a) => a -> a > next v = if (fromEnum v) == (fromEnum maxBound) > then minBound > else succ v I don't think this will quite work if fromEnum:: a -> Int for type a, were not injective. However, that might be part of the specification... I don't remember. It should be fine, so long as the preimage of (fromEnum maxBound) is {maxBound}. -Arjun -- Arjun Guha <guhaarju(a)grinnell.edu>

1 0

Some random newbie questions
by Benjamin Pierce 09 Jan '05

09 Jan '05

OK, I'm taking the plunge and using Haskell in a course I'm teaching this semester. To get ready, I've been doing quite a bit of Haskell programming myself, and this has raised a few questions... * What are the relative advantages of Hugs and GHC, beyond the obvious (Hugs is smaller and easier for people not named Simon to modify, while GHC is a real compiler and has the most up-to-date hacks to the type checker)? Do people generally use one or the other for everything, or are they similar enough to use Hugs at some moments and GHC at others? * As far as I can determine, there is no way to check pattern matches for exhaustiveness. Coming from OCaml, this feels like losing a significant safety net! How do people program so as not to be getting dynamic match failures all the time? * HUnit and QuickCheck seem to offer very nice -- but different -- testing facilities. Has anyone thought of combining them? (In fact, is HUnit actually used? The last revision seems to be a couple of years ago.) * I wrote a little program for generating Sierpinkski Carpets, and was astonished to find that it runs out of heap under Hugs (with standard settings -- raising the heap size with -h leads to a happier result). module Main where import SOEGraphics fillSquare w x y s = drawInWindow w (withColor Blue (polygon [(x,y), (x+s,y), (x+s,y+s), (x,y+s), (x,y)])) carpet w x y s = if s < 8 then fillSquare w x y s else let s' = s `div` 3 in do carpet w x y s' carpet w (x+s') y s' carpet w (x+s'*2) y s' carpet w x (y+s') s' carpet w (x+s'*2) (y+s') s' carpet w x (y+s'*2) s' carpet w (x+s') (y+s'*2) s' carpet w (x+s'*2) (y+s'*2) s' main = runGraphics ( do w <- openWindow "Carpet" (700,700) carpet w 50 50 600 k <- getKey w closeWindow w ) I've clearly got a lot to learn about space usage in Haskell... can someone give me a hint about what is the problem here and how it might best be corrected? Thanks for any comments, Benjamin ----------------------------------------------------------------------------- BENJAMIN C. PIERCE, Professor Dept. of Computer & Information Science University of Pennsylvania +1 215 898-2012 3330 Walnut St. Fax: +1 215 898-0587 Philadelphia, PA 19104, USA http://www.cis.upenn.edu/~bcpierce -----------------------------------------------------------------------------

16 23

RE: Enum class
by Arjun Guha 09 Jan '05

09 Jan '05

Well, you already have succ:: (Enum a) => a -> a defined for all data of the Enum class. You also need Bounded so that you can check maxBound. This (untested) code should do it: > next:: (Enum a, Bounded a) => a -> a > next v = if (toEnum v) == (toEnum (maxBound)) > then minBound > else succ v -- Arjun Guha <guhaarju(a)grinnell.edu>

1 0

Re: Typed Lambda-Expressions withOUT GADTs
by oleg＠pobox.com 08 Jan '05

08 Jan '05

Ashley Yakeley wrote on the first day of 2005: > This compiled with today's CVS GHC 6.3. I don't think you can do this > without GADTs. It seems we can do without GADT -- roughly with the same syntax (actually, the syntax of expressions is identical -- types differ and we have to write `signatures' -- i.e., instance declarations). Tested with GHC 6.2.1. I especially liked the example test3 = (runExpression s) (runExpression k) (runExpression k) below. Its inferred type is -- :t test3: -- test3 :: forall r. r -> r so, SKK must be the identity (if it terminates, that is) {-# OPTIONS -fglasgow-exts #-} {-# OPTIONS -fallow-undecidable-instances #-} module Expression where -- data Sym env r where -- FirstSym :: Sym (r,xx) r -- NextSym :: Sym env r -> Sym (a,env) r class SymT t env r data FirstSym = FirstSym deriving Show data NextSym t = NextSym t deriving Show instance SymT FirstSym (r,xx) r instance SymT t env r => SymT (NextSym t) (a,env) r class SymT t env r => RunSym t env r | t env -> r where runSym :: t -> env -> r -- runSym FirstSym (r,xx) = r; instance RunSym FirstSym (r,xx) r where runSym _ (r,xx) = r instance RunSym var env r => RunSym (NextSym var) (a,env) r where runSym (NextSym var) (a,env) = runSym var env -- the code literally -- data OpenExpression env r where -- Lambda :: OpenExpression (a,env) r -> OpenExpression env (a -> r); -- Symbol :: Sym env r -> OpenExpression env r; -- Constant :: r -> OpenExpression env r; -- Application :: OpenExpression env (a -> r) -> OpenExpression env a -> -- OpenExpression env r -- Frankly speaking, the class OpenExpression below isn't necessary -- We could have gotten by with just RunOpenExpression -- However, the class OpenExpression makes it easy to formulate -- the constraint for well-formed expressions. -- We can use that constraint elsewhere. class OpenExpression t env r data Lambda a t = Lambda t deriving Show data Symbol t = Symbol t deriving Show data Constant r = Constant r deriving Show data Application a t1 t2 = Application t1 t2 deriving Show instance OpenExpression t (a,env) r => OpenExpression (Lambda a t) env (a->r) instance SymT t env r => OpenExpression (Symbol t) env r instance OpenExpression (Constant r) env r instance (OpenExpression t1 env (a->r), OpenExpression t2 env a) => OpenExpression (Application a t1 t2) env r class OpenExpression t env a => RunOpenExpression t env a | t env -> a --class RunOpenExpression t env a | t env -> a where runOpenExpression :: t -> env -> a instance RunOpenExpression (Constant r) env r where runOpenExpression (Constant r) _ = r instance (RunOpenExpression t1 env (b->a), RunOpenExpression t2 env b) => RunOpenExpression (Application b t1 t2) env a where runOpenExpression (Application t1 t2) env = (runOpenExpression t1 env) (runOpenExpression t2 env) instance RunSym var env r => RunOpenExpression (Symbol var) env r where runOpenExpression (Symbol var) env = runSym var env instance RunOpenExpression t (a,env) r => RunOpenExpression (Lambda a t) env (a->r) where runOpenExpression (Lambda exp) env = \a -> runOpenExpression exp (a,env) newtype Expression t r = MkExpression (forall env. RunOpenExpression t env r => t) runExpression (MkExpression e) = runOpenExpression e () sym0 = Symbol FirstSym sym1 = Symbol (NextSym FirstSym) sym2 = Symbol (NextSym (NextSym FirstSym)) -- k = \x.\y -> x = \.\.1 k = MkExpression (Lambda (Lambda sym1)) -- s :: Expression ((a -> b -> c) -> (a -> b) -> a -> c); -- -- s = \x.\y.\z -> x z (y z) = \.\.\.2 0 (1 0) s = MkExpression (Lambda (Lambda (Lambda (Application (Application sym2 sym0) (Application sym1 sym0))))) test1 = (runExpression k) sym0 sym2 test2 = (runExpression k) sym2 sym0 test3 = (runExpression s) (runExpression k) (runExpression k) -- Note: That can only be the identity! -- :t test3: -- test3 :: forall r. r -> r test3' = test3 "It's the identity!!! Look at the type!!!"

10 20

Two fun things with GADTs
by Ashley Yakeley 08 Jan '05

08 Jan '05

1. Reifying class instances Easy to do, and useful sometimes: data MyMonad m where MkMyMonad :: (Monad m) => MyMonad m myReturn :: MyMonad m -> a -> m a myReturn MkMyMonad = return myBind :: MyMonad m -> m a -> (a -> m b) -> m b myBind MkMyMonad = (>>=) Note this may not yet be available in GHC CVS, see bug #1097046. 2. Casting among a limited set of types data Witness a where BoolWitness :: Witness Bool IntWitness :: Witness Int ListWitness :: Witness a -> Witness [a] data ComposeT p q a = MkComposeT {unComposeT p (q a)} witnessCast :: Witness a -> Witness b -> p a -> Maybe (p b) witnessCast BoolWitness BoolWitness pa = Just pa; witnessCast IntWitness IntWitness pa = Just pa; witnessCast (ListWitness wa) (ListWitness wb) pla = fmap unComposeT (witnessCast wa wb (MkComposeT pla)) witnessCast _ _ _ = Nothing; class Castable a where witness :: Witness a instance Castable Bool where witness = BoolWitness instance Castable Int where witness = IntWitness instance (Castable a) => Castable [a] where witness = ListWitness witness cast :: (Castable a,Castable b) => p a -> Maybe (p b) cast = witnessCast witness witness castOne :: (Castable a,Castable b) => a -> Maybe b castOne a = fmap runIdentity (cast (Identity a)) -- Ashley Yakeley, Seattle WA

1 0

The Implementation of Functional Programming Languages
by Simon Peyton-Jones 08 Jan '05

08 Jan '05

I'm happy to announce that my out-of-print 1987 book, The Implementation of Functional Programming Languages is now available online at http://research.microsoft.com/%7Esimonpj/papers/slpj-book-1987/index.htm Very many thanks to Marnie Montgomery, who did all the work. Happy reading Simon

2 1

RE: [Haskell-cafe] Unicode: Hugs vs GHC (again) was: Re: Some random newbie questions
by Simon Marlow 07 Jan '05

07 Jan '05

On 07 January 2005 13:01, Dimitry Golubovsky wrote: > Lennart Augustsson wrote: >> Simon Marlow wrote: >> >>> Here's a summary of the state of Unicode support in GHC and other >>> compilers. There are several aspects: >>> >>> - Can the Char type hold the full range of Unicode characters? >>> This has been true in GHC for some time, and is now true in Hugs. >>> I don't think it's true in nhc98 (please correct me if I'm >>> wrong). > > I remember, it was in GHC. But any attempt to output Unicode > characters using standard I/O functions always ended up outputting > only low 8 bits. Has anything changed since then? No, that's still the case (I mentioned it in a separate point in that message). >>> - Do the character class functions (isUpper, isAlpha etc.) work >>> correctly on the full range of Unicode characters? This is true >>> in Hugs. It's true with GHC on some systems (basically we were >>> lazy and used the underlying C library's support here, which is >>> patchy). > > Which basically means that one with older or underconfigured system > where they do not have permissions/technical possibilities to > configure locales in the C library properly is out of luck... True. Anyone care to take Hugs' implementation of the character class functions and put it in GHC? > The reason I asked this question was: I am trying to understand, where > is internationalization of Haskell compilers on their developers' list > of priorities, and also how high is demand from users to have at least > basic internationalization. We're keen to have it. The more people that complain about the lack of it, the faster it'll get done, probably :-) Cheers, Simon

2 1

Preventing space leaks without seq (was: Re: [Haskell-cafe] Some random newbie questions)
by Henk-Jan van Tuyl 07 Jan '05

07 Jan '05

L.S., Olaf <O.Chitil(a)kent.ac.uk> wrote: > I'm constantly surprised hearing from so many people about their space > problems. I cannot remember having space problems with my programs. I > don't know what everybody else is doing wrong I do disagree with > people recommending strictness annotations (seq etc). In contrast, I make > my programs as lazy as possible. Can you give some rules and/or examples how you do this? Henk-Jan van Tuyl -- Using Opera's revolutionary e-mail client: https://secure.bmtmicro.com/opera/buy-opera.html?AID=789433

1 0

Implementing computations with timeout
by Einar Karttunen 07 Jan '05

07 Jan '05

Hello What is the best way of doing an computation with a timeout? A naive implementation using two threads is easy to create - but what is the preferred solution? withTimeout :: forall a. Int -> IO a -> IO (Maybe a) withTimeout time fun = do mv <- newEmptyMVar tid <- forkIO (fun >>= tryPutMVar mv . Just >> return ()) forkIO (threadDelay time >> killThread tid >> tryPutMVar mv Nothing >> return ()) takeMVar mv btw How would I do the same with the new STM abstraction? - Einar Karttunen

4 10