December 2000 - Haskell

tuple component functions
by trb＠eastpac.com.au 03 Jan '03

03 Jan '03

S.D.Mechveliani writes: > As Haskell has the standard functions fst, snd to decompose (a,b), > maybe, it worths to provide also > tuple31, tuple31, tuple31, > ... > tuple51, tuple52, tuple53, tuple54, tuple55 > > for the tuples of n = 3,4,5 ? I've found some of these useful, except I named them differently: > fst3 :: (a,b,c) -> a > fst3 (x,_,_) = x > snd3 :: (a,b,c) -> b > snd3 (_,x,_) = x > thd3 :: (a,b,c) -> c > thd3 (_,_,x) = x .... never got around to quadruples etc. I also defined (some of these may be untested): > tripl :: a -> (a,a,a) > tripl x = (x,x,x) > curry3 :: ((a, b, c) -> d) -> a -> b -> c -> d > curry3 f x y z = f (x, y, z) > uncurry3 :: (a -> b -> c -> d) -> ((a, b, c) -> d) > uncurry3 f t = f (fst3 t) (snd3 t) (thd3 t) > applyTriple :: (a -> b, a -> c, a -> d) -> a -> (b,c,d) > applyTriple (f,g,h) x = (f x, g x, h x) > cross3 :: (a -> b, c -> d, e -> f) -> (a,c,e) -> (b,d,f) > cross3 (f,g,h) (x,y,z) = (f x, g y, h z) > mapTriple :: (a -> b) -> (a, a, a) -> (b, b, b) > mapTriple = cross3 . tripl > applyFst3 :: (a -> b) -> (a, c, d) -> (b, c, d) > applyFst3 f = applyTriple (f . fst3, snd3, thd3) > applySnd3 :: (a -> b) -> (c, a, d) -> (c, b, d) > applySnd3 f = applyTriple (fst3, f . snd3, thd3) > applyThd3 :: (a -> b) -> (c, d, a) -> (c, d, b) > applyThd3 f = applyTriple (fst3, snd3, f . thd3) > applyArgs3 :: (a -> b) -> (c -> d) -> (e -> f) -> (b -> d -> f -> g) -> (a -> c -> e -> g) > applyArgs3 af1 af2 af3 f = \x y z -> f (af1 x) (af2 y) (af3 z) > rotl :: (a -> b -> c -> d) -> (b -> c -> a -> d) > rotl f y z x = f x y z > rotr :: (a -> b -> c -> d) -> (c -> a -> b -> d) > rotr f z x y = f x y z > rotl4 :: (a -> b -> c -> d -> e) -> (b -> c -> d -> a -> e) > rotl4 f y z t x = f x y z t > rotr4 :: (a -> b -> c -> d -> e) -> (d -> a -> b -> c -> e) > rotr4 f t x y z = f x y z t Some more combinators (only for pairs so far): > twin :: a -> (a,a) > twin x = (x,x) > swap :: (a,b) -> (b,a) > swap (x,y) = (y,x) -- apply a pair of functions to one argument > applyPair :: (a -> b, a -> c) -> a -> (b, c) > applyPair (f, g) x = (f x, g x) -- apply a pair of functions to a pair > cross :: (a -> b, c -> d) -> (a, c) -> (b, d) > cross (f, g) = applyPair (f . fst, g . snd) -- compose a pair of functions onto one function > dotPair :: (a -> b, a -> c) -> (d -> a) -> (d -> b, d -> c) > dotPair (f, g) h = (f . h, g . h) -- compose a pair of functions onto a pair of functions > dotCross :: (a -> b, c -> d) -> (e -> a, f -> c) -> (e -> b, f -> d) > dotCross (f, g) (h, i) = (f . h, g . i) > mapPair :: (a -> b) -> (a, a) -> (b, b) > mapPair = cross . twin > applyFst :: (a -> b) -> (a, c) -> (b, c) > applyFst f = applyPair (f . fst, snd) > applySnd :: (a -> b) -> (c, a) -> (c, b) > applySnd f = applyPair (fst, f . snd) > applyArgs :: (a -> b) -> (c -> d) -> (b -> d -> e) -> (a -> c -> e) > applyArgs af1 af2 f = \x y -> f (af1 x) (af2 y) > betweenFst :: (a -> b -> c) -> (a, d) -> (b, e) -> c > betweenFst = applyArgs fst fst > betweenSnd :: (a -> b -> c) -> (d, a) -> (e, b) -> c > betweenSnd = applyArgs snd snd I find these combinators useful, and probably other people have their own versions - it would be nice to get them standardised, so we all speak the same language. By standardised, I mean a prominent version that will be adopted by users, not necessarily a committee process. Tim

3 2

ICFP programming contest
by trb＠eastpac.com.au 03 Jan '03

03 Jan '03

Michael Hobbs writes: > Just took a look at the results for the ICFP contest. Am I correct in > assuming that "LA" stands for Lennart Augustsson and that "Si^3" stands > for Simon Marlow, Simon Peyton-Jones, Sigbjorn Finne? Is there a URL for the results ? Tim

2 1

CFP: JFP on SAIG
by Walid Taha 08 Jul '01

08 Jul '01

CALL FOR PAPERS A Special Issue of JFP on Semantics, Applications, and Implementation of Program Generation http://cs-www.cs.yale.edu/~taha/saig/jfp.html Program generation has the prospect of being an integral part of a wide range of software development processes. Recent studies investigate different aspects of program generation systems, including their semantics, their applications, and their implementation. Existing theories and systems address both high-level (source) language and low-level (machine) language generation. A number of programming languages now support program generation and manipulation. These languages can have different goals, use different different implementation techniques, and target different applications. In this context, a PLI workshop dedicated to this theme (SAIG'00) was held this year. Following on from this workshop, a special issue of the Journal of Functional Programming will be devoted to the same theme. Full-length, archival-quality submissions are solicited on topics including both theoretical and practical models and tools for building program generation systems, Examples include: * Semantics, type systems, and implementations for multi-stage languages. * Run-time specialization systems: e.g. compilers, operating systems. * High-level program generation (applications, foundations, environments). * Symbolic computation, linking and explicit substitution, in-lining and macros. Reports on applications of these techniques to real-world problems are especially encouraged, as are submissions that relate ideas and concepts from several of these topics, or bridge the gap between theory and practice. Contributors to SAIG'00 are encouraged to submit, but submission is open to everyone. Papers will be reviewed as regular JFP submissions, and acceptance in the special issue will be based on relevance to the theme. The special issue also welcomes high-quality survey and position papers that would benefit a wide audience. Accepted papers exceeding the space restrictions will be published as regular JFP papers. Submissions should be sent to the guest editor (address below), with a copy to Nasreen Ahmad (nasreen(a)dcs.gla.ac.uk) Submitted articles should be sent in postscript format, preferably gzipped and uuencoded. In addition, please send, as plain text, title, abstract, and contact information. The submission deadline is February 1st, 2001. For other submission details, please consult an issue of the Journal of Functional Programming or see the Journal's web page at http://www.dcs.gla.ac.uk/jfp/. Guest Editor Editor in Chief Walid Taha Department of Computer Science Philip Wadler Yale University Avaya Labs P.O. Box 208285 700 Mountain Ave, Room 2T-402, New Haven, CT 06520-8285, Murray Hill, NJ 07974-0636, USA. USA. Email: taha(a)cs.yale.edu Email: wadler(a)avaya.com Phone: +1 203 432 6496 Phone: +1 908 582 4004 Fax : +1 203 432 0593 Fax: +1 908 582 5857

1 5

Disjoint type classes
by Jose Emilio Labra Gayo 05 Mar '01

05 Mar '01

I have a large program where I would like to include disjoint type classes into a new type class. My problem can be reduced to the following example (taken from [1]): > class Num a => Dividable a > where dividedBy :: a -> a -> a > instance Fractional a => Dividable a where > dividedBy = (/) > instance Integral a => Dividable a where > dividedBy = div Which doesn't work because Haskell doesn't detect that "Integral" and "Fractional" are disjoint. Is there a way to implement these type classes with current Haskell implementations? [1] K. Glynn, M. Sulzmann, P.J. Stuckey Type Classes and Constraint Handling Rules http://www.cs.mu.oz.au/tr_submit/test/cover_db/mu_TR_2000_7.html Best regards, Jose Labra

2 1

RE: Finding primes using a primes map with Haskell and Hugs98
by Simon Peyton-Jones 17 Jan '01

17 Jan '01

| Another way to do this is to compute the final array directly, | instead of computing successive versions of the array: | | import Array | primes n = [ i | i <- [2 ..n], not (primesMap ! i)] where | primesMap = accumArray (||) False (2,n) multList | multList = [(m,True) | j <- [2 .. n `div` 2], m <- | multiples j] | multiples j = takeWhile (n>=) [k*j | k <- [2..]] This style is definitely the way to go. Haskell does badly if you update an array one index at a time. Remember that arrays can be recursive. Here's a definition of Fibonacci for example; you can probably adapt it for primes fibs :: Int -> Array Int Int -- If a = fibs n, then a!i is fib(i), for i<=n. fibs n = a where a = array (1,n) ([(1,1),(2,1)] ++ [(i,a!(i-1) + a!(i-2) | i <- [3..n]]) -- Notice that a is recursive Simon

4 3

Are fundeps the right model at all?
by qrczak＠knm.org.pl 15 Jan '01

15 Jan '01

Could somebody show an example which requires fundeps and cannot be expressed using a simpler model explained below - a model that I can even understand? Is the model self-consistent at all? Each class is associated with a set of subsets of type variables in its head. Let's call it the set of keys. The intuitive meaning of a key is that types corresponding to these variables are sufficient to determine which instance to choose. They correspond to lhss of some fundeps. Plain classes without explicitly written keys correspond to having a single key consisting of all type variables. Keys influence the typechecking thus: - A type is unambiguous if for every class constraint in it there exists its key such that types in the constraint corresponding to type variables from the key contain no type variables which are absent in the type itself. - All class methods must have unambiguous types, i.e. for each method there must be a key whose all type variables are present in the method's type. - For each key, there must be no pair of instances whose heads projected to the class parameters from the key overlap. - For each class constraint of an unambiguous type an each its key there must be an instance found basing on this key, or the type is incorrect because of missing instances. Moreover, instances found basing on all keys must be identical. - Perhaps something must be said about class contexts and instance contexts. I'm not sure what yet. Examples: class Collection c e | c where empty :: c insert :: c -> e -> c class Monad m => MonadState s m | m where get :: m s put :: s -> m () newtype State s a = State {runState :: s -> (a,s)} instance Monad (State s) instance MonadState s (State s) test1:: Int -> Int test1 x = snd (runState get x) -- Not ambiguous. class IOvsST io st | io, st where -- Two single-element keys. ioToST :: io -> st stToIO :: st -> io instance IOvsST (IORef a) (STRef s a) where ioToST = unsafeCoerce# stToIO = unsafeCoerce# test2:: IORef a -> IORef a test2 = ioToST . stToIO -- Not ambiguous. class Foo a b | a instance Foo Int [a] -- This is rejected by Hugs (with fundep a->b) but I would definitely -- accept it. -- __("< Marcin Kowalczyk * qrczak(a)knm.org.pl http://qrczak.ids.net.pl/ \__/ ^^ SYGNATURA ZASTÊPCZA QRCZAK

8 14

RE: Problem with functional dependencies
by Simon Peyton-Jones 04 Jan '01

04 Jan '01

I think you can simplify the example. Given class HasFoo a b | a -> b where foo :: a -> b instance HasFoo Int Bool where ... Is this legal? f :: HasFoo Int b => Int -> b f x = foo x You might think so, since HasFoo Int b => Int -> b is a substitution instance of HasFoo a b => a -> b but if we infer the type (HasFoo Int b => Int -> b) for f's RHS, we can then "improve" it using the instance decl to (HasFoo Int Bool => Int -> Bool), and now the signature isn't a substitution insance of the type of the RHS. Indeed, this is just what will happen if you try with GHC, because GHC takes advantage of type signatures when typechecking a function defn, rather than first typechecking the defn and only then comparing with the signature. I don't know what the answers are here, but there's more to this functional dependency stuff than meets the eye. Even whether one type is more general than another has changed! Simon | -----Original Message----- | From: qrczak(a)knm.org.pl [mailto:qrczak@knm.org.pl] | Sent: 17 December 2000 19:30 | To: haskell(a)haskell.org | Subject: Problem with functional dependencies | | | The following module is rejected by both | ghc -fglasgow-exts -fallow-undecidable-instances | and | hugs -98 | | -------------------------------------------------------------- | ---------- | class HasFoo a foo | a -> foo where | foo :: a -> foo | | data A = A Int | data B = B A | | instance HasFoo A Int where | foo (A x) = x | | instance HasFoo A foo => HasFoo B foo where | foo (B a) = foo a | -------------------------------------------------------------- | ---------- | | The error messsage says that the type inferred for foo in B's instance | is not general enough: the rhs has type "HasFoo B Int => B -> | Int", but | "HasFoo B foo => B -> foo" was expected.

6 8

Learning Haskell and FP
by Doug Ransom 04 Jan '01

04 Jan '01

I have read "The Craft of Functional Programming" by Simon Thompson and a few paper on the web. "The Craft" is a good book, but it is an introduction to FP. It seems to me it there are a lot of books on OO design I can pick up at the bookstore, but in the FP world, one must worm their way through all sorts of papers. I have seen papers on Catamorphisms, Monads, Programming with Barbed Wire, folds, etc. I think these papers are hard to understand if you don't have the acadademic/mathematical background -- being papers and not textbooks these papers assume a fair bit of base knowledge. I know I can design a fold function to use in place of primitive recursion for most data structures -- I just don't know if I should. It is pretty easy to get through "The Craft of Functional Programming" without understanding what Category Theory , a Catamorphism , or a Kleisli Composition is. I can see lots of real Software Engineering oppurtunities for these various techniques if I could just put them together. Is there a good textbook on Functional Programming which starts from a base point similar to "The craft of Functional Programming" but more advanced in terms of introducing necessary topics like Category theory, catamorphisms, monads, etc? I would find such a book very useful, especially if it concentrated on lazy functional programming. Doug Ransom Systems Engineer Power Measurement Ltd. http://www.pml.com 250-652-7100 office 250-652-0411 fax mailto:doug_ransom@pml.com

15 21

The Hanoi Towers
by R.Daniel 30 Dec '00

30 Dec '00

hi, i was looking for the source code for the Hanoi Towers, if anyone has that, could you please send it to me? I apreciate the help , thankx ----->R.Daniel Aka AZONIC ICQ 28959546

1 0

Haskell Language Design Questions
by Doug Ransom 30 Dec '00

30 Dec '00

1. Is the lack of dynamic binding of functions by design or because it was too much effort to be justified at the time the language was designed? In object oriented programming there can be several implementations of the same interface, and they can be stored in the same collection. 2. It seems to me that the Maybe monad is a poor substitute for exception handling because the functions that raise errors may not necessarily support it. For example, if I use someone elses custom type and a custom map function theirmap myApplicator SomeList and theirmap is not designed to support the Maybe monad, then it becomes hard to use if SomeFunction might raise an error. Am I missing something? Doug Ransom Systems Engineer Power Measurement Ltd. http://www.pml.com 250-652-7100 office 250-652-0411 fax mailto:doug_ransom@pml.com

3 2