- Haskell-Cafe - Haskell.org

Using Haskell as a database
by Dmitri Pissarenko 10 Jan '05

10 Jan '05

Hello! I am thinking about writing a system, using which it is possible to store information about the structure of a bureaucratic system. Coarse-grained features of the program include: 1) The program should allow the user to enter the hierarchy (like: authority X has a board of Y members, each of them has Z departments under his/her control etc) of a governmental organization 2) The program should visualize the hierarchy in form of a tree 3) It should be possible to enter information about what areas of public administration a particular civil servant is responsible for. In other words: If things go wrong in some domain, controlled by the government, the user should be able to figure out, who is responsible for that mess. My first idea was to use a relational database for storing this information. However, a relational database may be inefficient due to the complexity of the data structure. At the moment, I think that it makes more sense to store the data in form of facts (not tables as in relational database). I mean that one is able to enter statements like (this is PROLOG syntax) isOrganization(X). hasBoard(X, Members) :- isOrganization(X), isList(Members). civilServant(X). isResponsibleFor(X, Y) :- civilServant(X), domain(Y). and then run queries, using which one can find out, which organizations are there, what members they have etc. Can one do this in Haskell? Thanks in advance Dmitri Pissarenko

2 1

Re: Some random newbie questions
by John Hughes 10 Jan '05

10 Jan '05

I seriously considered switching frlom Hugs to GHC for my introductory programming class this year, but in the end stayed with Hugs because of a single feature. I'm teaching beginning programmers, and for them at least, there is an overwhelming volume of names to learn -- "what's that function?" is a question they ask themselves often, as is "what's that type?". I teach them that, whenever they see a name they don't recognise, they can find out more about it using the :i command. This is a simple trick to learn, that helps them understand points they've missed and catches misapprehensions. My students also see type classes very early. I'll bet yours will too. Even if one is very careful to restrict the examples in lectures so as to avoid them (which is a bind), as soon as students try out Hugs for themselves, they will make mistakes that generate error messages referring to type classes. No problem: the question "what's that class?" can ALSO be answered by :i. Now, at the beginning students have only a very rudimentary understanding of classes. A class is a collection of types to them, nothing more. In particular, the class definition itself is of little use to them, since it often contains a very subtly chosen collection of methods (just type :i Show, for example, which students do very early). What IS useful, right from the beginning, is the list of instances. What are Num types? Oh, integers and reals. What are Show types? Oh, pretty much everything. Particularly when debugging "missing instance" errors, this is just the information you need. Unfortunately, while Hugs prints the list of instances of a class in response to :i, GHCi does not. It only prints the class definition -- which, for my students, contains no useful information. For that reason alone, I stuck with Hugs last year. Of course, later in the course there is no problem in introducing GHC as well. Students coping well are happy to learn there is a compiler available too, while those who are struggling can stay with Hugs throughout the course. I demonstrated GHC in order to show them wxHaskell (which was very popular with the students), but I didn't REQUIRE them to use it. How about changing the behaviour of :i, Simon, so I can use GHCi throughout next year? John

3 3

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 10 Jan '05

10 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 09 Jan '05

09 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 08 Jan '05

08 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