June 2005 - Haskell-Cafe

RE: [Haskell-cafe] Re: Using type classes for polymorphism of dataconstructors
by Ralf Lammel 23 Jun '05

23 Jun '05

Thomas Sutton wrote: > Main> :t (Impl (Prop "p") (Poss (Prop "p"))) -- "p -> <>p" > Impl (Prop "p") (Poss (Prop "p")) :: PC So the type says that this is a formula in the predicate calculus? (Even though you combine two formulae of modal logics.) Are you happy with that? Just wondering? Also, are you fine to take the conjunction of a PC and Modal formula, which is admitted by your types? (If not, you may want to use phantom types.) So it seems like the type doesn't carry a lot of information. Then we could also use different types. In particular, we could do without existentials. The types we get will (additionally) record the arity of the outermost constructor. (In your model, the type records the kind of logic of the outermost constructor.) class (Show f) => Formula f data PC0 = Prop String data Formula x => PC1 x = Neg x data (Formula x, Formula y) => PC2 x y = Conj x y | Disj x y | Impl x y instance Formula PC0 instance Formula x => Formula (PC1 x) instance (Formula x, Formula y) => Formula (PC2 x y) instance Show PC0 where show (Prop s) = s instance Formula x => Show (PC1 x) where show (Neg x) = "~" ++ show x instance (Formula x, Formula y) => Show (PC2 x y) where show (Conj a b) = (show a) ++ " /\\ " ++ (show b) show (Disj a b) = (show a) ++ " \\/ " ++ (show b) show (Impl a b) = (show a) ++ " -> " ++ (show b) data Formula x => Modal1 x = Poss x | Necc x instance Formula x => Formula (Modal1 x) instance Formula x => Show (Modal1 x) where show (Poss a) = "<>" ++ (show a) show (Necc a) = "[]" ++ (show a) main = do print (Prop "p") print (Poss (Prop "p")) print (Impl (Prop "p") (Poss (Prop "p"))) (Again, just wondering whether this might be an Ok solution.) Thomas Sutton wrote: > > In Java (C#, Python, etc) I'd do this ... Please post your Java code. I might want to add it to the OOHaskell demo suite. Ralf > -----Original Message----- > From: haskell-cafe-bounces(a)haskell.org [mailto:haskell-cafe- > bounces(a)haskell.org] On Behalf Of Thomas Sutton > Sent: Thursday, June 23, 2005 3:27 AM > To: haskell-cafe(a)haskell.org > Subject: [Haskell-cafe] Re: Using type classes for polymorphism of > dataconstructors > > On 11/06/2005, at 11:18 PM, Thomas Sutton wrote: > > In Java (C#, Python, etc) I'd do this by writing an interface > > Formula and have a bunch of abstract classes (PropositionalFormula, > > ModalFormula, PredicateFormula, etc) implement this interface, then > > extend them into the connective classes Conjunction, Disjunction, > > etc. The constructors for these connective classes would take a > > number of Formula values (as appropriate for their arity). > > > > I've tried to implement this sort of polymorphism in Haskell using > > a type class, but I have not been able to get it to work and have > > begun to work on implementing this "composition" of logics in the > > DSL compiler, rather than the generated Haskell code. As solutions > > go, this is far from optimal. > > > > Can anyone set me on the right path to getting this type of > > polymorphism working in Haskell? Ought I be looking at dependant > > types? > > I've finally managed to find a way to get this to work using > existentially quantified type variables and am posting it here for > the benefit of the archives (and those novices like myself who will > look to them in the future). My solution looks something like the > following: > > A type class over which the constructors ought to be polymorphic: > > > class (Show f) => Formula f where > > language :: f -> String > > A type exhibiting such polymorphism: > > > data PC > > = Prop String > > | forall a. (Formula a) => Neg a > > | forall a b. (Formula a, Formula b) => Conj a b > > | forall a b. (Formula a, Formula b) => Disj a b > > | forall a b. (Formula a, Formula b) => Impl a b > > instance Formula PC where > > language _ = "Propositional Calculus" > > instance Show PC where > > show (Prop s) = s > > show (Neg s) = "~" ++ (show s) > > show (Conj a b) = (show a) ++ " /\\ " ++ (show b) > > show (Disj a b) = (show a) ++ " \\/ " ++ (show b) > > show (Impl a b) = (show a) ++ " -> " ++ (show b) > > Another such type: > > > data Modal > > = forall a. (Formula a) => Poss a > > | forall b. (Formula b) => Necc b > > instance Formula Modal where > > language _ = "Modal Logic" > > instance Show Modal where > > show (Poss a) = "<>" ++ (show a) > > show (Necc a) = "[]" ++ (show a) > > Some example values of those types: > > Main> :t (Prop "p") -- "p" > Prop "p" :: PC > > Main> :t (Poss (Prop "p")) -- "<>p" > Poss (Prop "p") :: Modal > > Main> :t (Impl (Prop "p") (Poss (Prop "p"))) -- "p -> <>p" > Impl (Prop "p") (Poss (Prop "p")) :: PC > > I also have a sneaking suspicion I'd also be able to solve this > problem using dependant types, but I have not investigated that > approach. > > Cheers, > Thomas Sutton > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe

1 0

Using type classes for polymorphism of data constructors
by Thomas Sutton 23 Jun '05

23 Jun '05

Hi all, I've just started working on a theorem prover (labelled tableaux in case anyone cares) in Haskell. In preparation, I've been attempting to define some data types to represent logical formulae. As one of the requirements of my project is generality (i.e. it must be easily extendible to support additional logics), I've been attempting to build these data types modularly. The end goal in all of this is that the user (perhaps a logician rather than a computer scientist) will describe the calculus they wish to use in a simple DSL. This DSL will then be translated into Haskell and linked against some infrastructure implementing general tableaux bits and pieces. These logic implementations ought to be composable such that we can define modal logic to be propositional calculus with the addition of [] and <>. In Java (C#, Python, etc) I'd do this by writing an interface Formula and have a bunch of abstract classes (PropositionalFormula, ModalFormula, PredicateFormula, etc) implement this interface, then extend them into the connective classes Conjunction, Disjunction, etc. The constructors for these connective classes would take a number of Formula values (as appropriate for their arity). I've tried to implement this sort of polymorphism in Haskell using a type class, but I have not been able to get it to work and have begun to work on implementing this "composition" of logics in the DSL compiler, rather than the generated Haskell code. As solutions go, this is far from optimal. Can anyone set me on the right path to getting this type of polymorphism working in Haskell? Ought I be looking at dependant types? Thanks in advance, Thomas Sutton

2 3

Compiling ghc with openal
by Ron 22 Jun '05

22 Jun '05

Hi, I am configuring ghc from source(no Ports(since that is broken for this purpose too)) on freebsd 5.4: CPPFLAGS="-I/usr/X11R6/include/ -I/usr/local/include/ -L/usr/local/lib/ " ./configure I had issues with opengl, which were resolved by adding the first dir to CPPFLAGS, but it seems impossible to get ghc to recongize OpenAL, while I have it in /usr/local/lib libogg.a libogg.so libopenal.a libopenal.so.0 liborbit-c-backend.a libogg.la libogg.so.5 libopenal.so libopenal.so.0.0.8 In /usr/local/include/AL, I have al.h alc.h alctypes.h alext.h alexttypes.h altypes.h alut.h aluttypes.h I get this: checking for library containing alGenSources... no configure: WARNING: no OpenAL library found, so this package will not be built So, basically the question is: how do I tell ghc to "find" OpenAL? Regards, Ron

1 0

Buddha and GHC 6.4
by Jim Apple 20 Jun '05

20 Jun '05

Has anyone gotten Buddha (now called "plargleflarp" http://www.cs.mu.oz.au/~bjpop/buddha/) do work with GHC 6.4? I'm getting ghc-6.4: unknown package: buddha Jim P.S. What happened to the old name?

4 6

Announcing cross-platform implementation of Pan
by Sean Seefried 19 Jun '05

19 Jun '05

Hi all, I'd like to announce a new cross-platform implementation of Conal Elliott's image synthesis language - Pan. For more information see: http://www.cse.unsw.edu.au/~sseefried/pan/ This is very much an alpha release of the software. I have only built and tested it on Mac OS X and Linux, although it has been tested on Windows by another. Features: * Uses Don Stewart's hs-plugins library to dynamically load and display effects. * Cross-platform. Uses Daan Leijen's wxHaskell and Sven Panne's HOpenGL libraries. * Uses the Haskell Cabal libraries. Builds with version released in GHC 6.4. Drawbacks: * Not as fully featured as the original. * Not as fast. Implemented directly in Haskell instead of generating C code. Sean

1 0

Functional Programming lecture on video
by Carsten Otto 17 Jun '05

17 Jun '05

Hello! I am student at the RWTH Aachen (Germany) and this semester professor Giesl is lecturing "Functional Programming". In the first part of this lecture Haskell is presented and all basic concepts are explained (recursion, pattern matching, lambda expressions, user declared data types, ...). Later in this lecture the theoretical background is the main topic (semantics, lambda calculus, ...). If you are interested, you can watch this lecture on video: http://video.s-inf.de/#FP.2005-SS-Giesl.(COt).HD_Videoaufzeichnung The lecture of course is being held in English. The video is encoded with XviD 1250 KBit and 64 KBit Mono-MP3. The download-server is connected with about 100 MBit, so your download should be quite fast. Have fun, -- Carsten Otto carsten.otto(a)gmail.com www.c-otto.de

1 0

Hugs parse error in library file
by james pentland 16 Jun '05

16 Jun '05

i am working on ch 15, School of Expression. unfortunately, import Memo causes an Hugs error (see below). also, memoB in ch 15 calls memo1, but there is no memo1 in h:\Program Files\Hugs98\libraries\Hugs\Memo.hs this module contains memoN :: Int -> (a -> b) -> (a -> b) memoN = mkMemo eql hash of course, it should be easy enough to write memo1 :: (a -> b) -> (a -> b) memo1 = memoN 1 Memo.hs imports ST, which is where Hugs reports a parse error. h:\Program Files\Hugs98\libraries\Hugs\ST.hs contains at line 50 newtype ST s a = ST (forall r. (a -> r) -> r) what is the workaround? pentland@thetis /ntd/lo $ hugs Hugs session for: H:\Program Files\Hugs98\libraries\Hugs\Prelude.hs H:\Program Files\Hugs98\libraries\Prelude.hs H:\Program Files\Hugs98\libraries\Hugs\Base.hs Type :? for help Hugs.Base> :v -- Hugs Version 20050113 Hugs.Base> :load xva ERROR "H:\Program Files\Hugs98\libraries\Hugs\ST.hs":50 - Syntax error in type expression (unexpected `.') Animation> pentland@thetis /ntd/lo $ cat xva.hs import Animation (picToGraphic) import Shape import Picture import Memo import SOEGraphics hiding (Region, Event) import qualified SOEGraphics as G (Region, Event) import Draw (xWin,yWin,intToFloat) import Win32Misc (timeGetTime) -- import Word (word32ToInt) import Channel type Time = Float type UserAction = G.Event newtype Behavior a = Behavior (([Maybe UserAction],[Time]) -> [a]) newtype Event a = Event (([Maybe UserAction],[Time]) -> [Maybe a]) time :: Behavior Time time = Behavior (\(_,ts) -> ts) __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com

2 1

(small) code review request
by Radu Grigore 16 Jun '05

16 Jun '05

The programming language I know best is C++. Wait, don't close the message. I also know OCaml and a couple of days ago I read "A Gentle Introduction to Haskell". In order to practice what I've learned a bit above "hello world" programs I chose to solve some easy tasks from SPOJ. They have automatic testing so I know if I got it right or not and I can also look at submission statistics (number and accuracy) to choose easy problems. Aside from "easiness" I've chosen at random these: https://spoj.sphere.pl/problems/ADDREV/ https://spoj.sphere.pl/problems/CRSCNTRY/ So these are my first two Haskell "programs" and I'd appreciate any comments you might have, especially better ways of solving the problems. The first one asks you to print rev(rev a + rev b) for two numbers a and b where rev is a function that transforms an integer into an integer you get by reversing the digits. --- BEGIN addrev.hs --- rev :: Int -> Int rev = read . reverse . show solve :: Int -> IO () solve 0 = do return () solve n = do line <- getLine let a:b:_ = words line an = read a bn = read b in (putStrLn . show . rev) (rev an + rev bn) solve (n-1) main = do hSetBuffering stdin LineBuffering line <- getLine solve (read line) --- END addrev.hs --- The second problem happens to be the Longest Common Subsequence problem, which is a classical DP problem. After searching a bit how to do memoisation/dp in Haskell I've found two resources: http://www.haskell.org/hawiki/MemoisingCafs http://portal.acm.org/citation.cfm?id=871896&coll=Portal&dl=ACM&CFID=461433… I chose to try the approach in the Bird&Hinze article. The result is my second Haskell program: --- BEGIN crscntry.lhs --- One of the problems at SPOJ, namely CRSCNTRY, asks you to implement the classical (DP) algorithm for finding the length of the longest common subsequence. The reccurence relation is: lcs [] _ = 0 lcs _ [] = 0 lcs (x:xs) (y:ys) = | x == y = 1 + lcs xs ys | otherwise = lcs (x:xs) ys `max` lcs xs (y:ys) There are of course only mn distinct calls to lcs, where m = 1 + length xs, n = 1 + length ys. I will try here a memoisation approach about which I have read in "Trouble shared is trouble halved", by Bird and Hinze. The basic idea is to explicitly construct the call tree and store in it the result of computing the function. First, note that the reccurence relation above makes either one or two calls. I think we can get by with a binary tree that has this invariant: left . right n = right . left n Let's define the tree. > data Tree a = Empty | Node { left :: Tree a, info :: a, right :: Tree a } > leaf :: a -> Tree a > leaf x = Node Empty x Empty Now imagine the tree nodes put into a matrix l l x <--- x <--- x ^ ^ ^ |r l |r l |r x <--- x <--- x We use two memoisation functions. One of them constructs all the rows above (memo_lcs), while the other reuses the nodes above and constructs only one row to the left (memo_lcs'). We also pass around the lists so that we can constructs nodes correctly. > memo_lcs :: Eq a => [a] -> [a] -> Tree Integer > memo_lcs [] _ = Empty > memo_lcs _ [] = Empty > memo_lcs (x:xs) (y:ys) = > node x y (memo_lcs' t xs (y:ys)) t > where t = memo_lcs (x:xs) ys > memo_lcs' :: Eq a => Tree Integer -> [a] -> [a] -> Tree Integer > memo_lcs' _ [] _ = Empty > memo_lcs' _ _ [] = Empty > memo_lcs' z (x:xs) (y:ys) = > node x y (memo_lcs' l xs (y:ys)) l > where l = tree_left z Both of these functions use a smart constructor. It takes the left and right branches and constructs a new node while also computing the correct value the function must have. > node :: Eq a => a -> a -> Tree Integer -> Tree Integer -> Tree Integer > node x y l r > | x == y = Node l (1 + (value . tree_left) r) r > | otherwise = Node l (value l `max` value r) r The inspection of the value returns 0 for empty nodes. > value :: Tree Integer -> Integer > value Empty = 0 > value (Node _ r _) = r You might be wondering by now what is the function tree_left. > tree_left :: Tree a -> Tree a > tree_left Empty = Empty > tree_left (Node l _ _) = l (I wonder if all this would be simpler if I'd use a border of 0-valued leafs instead of the functions tree_left and value. I'll try soon.) Now the definition of lcs is simple. > lcs :: Eq a => [a] -> [a] -> Integer > lcs x y = value (memo_lcs x y) This is the basic solution of the problem CRSCNTRY. A testcase is just a bit more complicated. > testcase :: [[Integer]] -> Integer > testcase (x:xs) = foldl max 0 (map (lcs x) xs) In order to finish we just need to take care of the IO. > myReadList :: String -> [Integer] > myReadList s = > let (a, t) = head (lex s) in > case read a of > 0 -> [] > n -> n : (myReadList t) > readTest :: IO [[Integer]] > readTest = do > line <- getLine > case myReadList line of > [] -> do return [] > lst -> do > rest <- readTest > return (lst : rest) The solve function reads n tests and solves each of them. > solve :: Integer -> IO () > solve 0 = return () > solve (n+1) = do > test <- readTest > putStrLn (show (testcase test)) > solve n In the main function we read the number of tests we should handle and then solve them > main = do > line <- getLine > solve (read line) That's it. I hope it works (fast enough). --- END crscntry.lhs --- It worked fast enough. Anyway, I was wondering if the O(n) space and O(n^2) time solution can be implemented in Haskell. Another way to ask this. Consider the classic fibonacci example. Can one compute the n-th fibonacci number in O(n) time and O(1) space, i.e. remember only the "last" two values during computation? -- regards, radu http://rgrig.blogspot.com/

2 3

RE: [Haskell-cafe] Garbage collection and finalizer thread priority
by Simon Marlow 16 Jun '05

16 Jun '05

On 13 June 2005 14:32, Gracjan Polak wrote: > Simon Marlow wrote: >> >> I presume you're running GHC. There's no way to increase the >> priority of a thread - GHC's scheduler doesn't have a concept of >> priorities. >> > > Yes, I forgot to state it explicitly. > >> I would look into whether you can use mallocForeignPtr: this is much >> faster than using newForeignPtr with finalizerFree, because the >> memory is garbage collected directly and there's no need for a >> finalizer. > > I use mallocBytes + reallocBytes + addForeignPtrFinalizer > finalizerFree. I wouldn't think this is any different, thanks for > your suggestion. > > May I ask where that difference comes from? mallocBytes allocates memory using C's malloc(), which is expensive. Also, the finalizer to free the memory is also expensive. mallocForeignPtr on the other hand allocates memory directly in GHC's heap (much faster than malloc()), and the memory is garbage collected when it is no longer referenced, so there's no need for the finalizer. Still, ForeignPtr is quite a bit slower than Ptr. We have some ideas for improving it, which I'll hopefully get round to implementing sometime. Cheers, Simon

1 0

RE: [Haskell-cafe] Garbage collection and finalizer thread priority
by Simon Marlow 16 Jun '05

16 Jun '05

On 13 June 2005 16:55, Sebastian Sylvan wrote: > On 6/13/05, Simon Marlow <simonmar(a)microsoft.com> wrote: > >> I presume you're running GHC. There's no way to increase the >> priority of a thread - GHC's scheduler doesn't have a concept of >> priorities. >> > > Just out of curiousity, what scheme does GHC use for scheduling > threads? Just round-robin, at the moment. Cheers, Simon

1 0