- Haskell-Cafe - Haskell.org

Re: Polymorphic lists...
by MR K P SCHUPKE 12 Mar '04

12 Mar '04

Just running through the implementation of some of the functions I mentioned, with the newtyped tuple version. Thought the run-time indexed code looked neat so I thought i'd post it: First the definition: newtype RNil = RNil () newtype RCons attribute relation = RCons (attribute,relation) class Relation relation instance Relation (RNil ()) instance Relation relation => Relation (RCons attribute relation) emptyRM :: RNil emptyRM = RNil () now the code: class Relation r => IndexRM' r a where indexRM' :: r -> Int -> Maybe a instance IndexRM' RNil a where indexRM' _ _ = Nothing instance IndexRM' r a => IndexRM' (RCons a r) a where indexRM' (RCons (a,_)) 0 = Just a indexRM' (RCons (_,r)) n = indexRM' r (n-1) instance IndexRM' r a => IndexRM' (RCons b r) a where indexRM' (RCons (_,_)) 0 = Nothing indexRM' (RCons (_,r)) n = indexRM' r (n-1) This finds the Nth value where 'n' is a normal integer. The last block repeats twice because one matches the case where the return type is the same, and the other is for then the return type and indexed value differ. This is why the return type is Maybe. With the compile time natural number lookup, the program will fail to compile if the types differ, but with the runtime lookup the type and the success cannot be determined (hence no functional dependancy) and returning Maybe makes the most sense. Regards, Keean.

1 0

Re: [Haskell-cafe] Haskell overview
by MR K P SCHUPKE 12 Mar '04

12 Mar '04

Is it just me or is "citeseer.nj.nec.com" down? Keean.

3 2

Re: [Haskell-cafe] Passing types as arguments
by MR K P SCHUPKE 12 Mar '04

12 Mar '04

You can pattern match on types - as I have been having much fun with recently ... you use multi-parameter type classes (with optional functional dependancies) to match types. Regards, Keean.

1 0

RE: [Haskell-cafe] Passing types as arguments
by Simon Peyton-Jones 12 Mar '04

12 Mar '04

We pass values as proxies for types extensively in the "Scrap your boilerplate" scheme. The paper is on my home page. The 'typeOf' function is a good example. Part II coming up shortly. Simon | -----Original Message----- | From: haskell-cafe-bounces(a)haskell.org [mailto:haskell-cafe-bounces@haskell.org] On Behalf Of | ajb(a)spamcop.net | Sent: 12 March 2004 03:50 | To: haskell-cafe(a)haskell.org | Subject: [Haskell-cafe] Passing types as arguments | | G'day everyone. | | Some time ago a suggestion came up about passing types as arguments | to functions: | | http://www.haskell.org/pipermail/haskell/2003-June/012184.html | | As a matter of curiosity, the topic has come up again on the wiki: | | http://haskell.org/hawiki/StudyGroup/GraphExamplesInHaskell/WhySum3 | | For this example, we don't just want to pass types, we also want to | pattern match on them. | | I'm curious if anyone else has put any thought to this idea. Is it just | a syntax issue, or are there bad interactions with other parts of the | type system? | | Cheers, | Andrew Bromage | _______________________________________________ | Haskell-Cafe mailing list | Haskell-Cafe(a)haskell.org | http://www.haskell.org/mailman/listinfo/haskell-cafe

2 1

Passing types as arguments
by ajb＠spamcop.net 12 Mar '04

12 Mar '04

G'day everyone. Some time ago a suggestion came up about passing types as arguments to functions: http://www.haskell.org/pipermail/haskell/2003-June/012184.html As a matter of curiosity, the topic has come up again on the wiki: http://haskell.org/hawiki/StudyGroup/GraphExamplesInHaskell/WhySum3 For this example, we don't just want to pass types, we also want to pattern match on them. I'm curious if anyone else has put any thought to this idea. Is it just a syntax issue, or are there bad interactions with other parts of the type system? Cheers, Andrew Bromage

1 0

Haskell overview
by ATWOOD,JOHN (HP-Corvallis,ex1) 12 Mar '04

12 Mar '04

> A colleague with a mathematics and Lisp background is wanting to learn > more about Haskell. The books he's looked at concentrate more on building > up from the basics and getting the syntax right, etc., whereas really he's > looking more of a top-down view that makes Haskell's features and behavior > clear and relates them to category theory, etc. Would anyone be able to > suggest some good references? > >-- Mark For lispers, I like to point out this sentence of section 6.4 of the Haskell 98 Report: Haskell provides several kinds of numbers; the numeric types and the operations upon them have been heavily influenced by Common Lisp and Scheme. For mathematicians, I'd recommend the first 5 pages of: Calculating Functional Programs, Jeremy Gibbons, 2002 http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/index.html# calculating Then I'd mention the Acid Rain Theorem, Fusion Theorem, Wadler's _Theorems for Free!_. When I'd show some exemplary fp programs: Bridging the Algorithm Gap: A Linear-Time Functional Program for Paragraph Formatting. Oege de Moor and Jeremy Gibbons, 1999 http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/index.html# para Financial Contracts: An Adventure in Financial Engineering, 2000 Simon Peyton Jones, Jean-Marc Eber, and Julian Seward http://www.lexifi.com/resources.html#paper Functional Specification of JPEG Decompression, and an Implementation for Free, Jeroen Fokker, 1995 http://citeseer.nj.nec.com/72092.html Modeling Web Interactions, Paul Graunke, Robert Bruce Findler, Shriram Krishnamurthi, Matthias Felleisen, 2003 http://citeseer.nj.nec.com/graunke03modeling.html Haskell Server Pages Functional Programming and the Battle for the Middle Tier, Erik Meijer, Dannyy van Velzen, 2000 http://citeseer.nj.nec.com/318262.html Writing High-Performance Server Applications in Haskell, Case Study: A Haskell Web Server, Simon Marlow, 2000 http://www.haskell.org/~simonmar/bib.html (about the 4th one down) And then, the more introductory material: Why Functional Programming Matters, John Hughes http://www.cs.chalmers.se/~rjmh/Papers/whyfp.html and here's a summary of the paper: http://www.cs.auckland.ac.nz/~j-hamer/360/why-fp-matters.html Section 3.1.3 of SICP: http://mitpress.mit.edu/sicp/ Why no one uses functional languages, Philip Wadler, 1998 http://citeseer.nj.nec.com/wadler98why.html here's an old, but still relevant summary of some issues keeping fp from taking over the world: http://www.cs.colorado.edu/~zorn/cs5535/Fall-1997/haskell-summary.html Some general links: http://haskell.readscheme.org/ http://www.haskell.org Hope this isn't too overwhelming, but it was an opportunity for me to gather my thoughts. Enjoy, John Atwood

1 0

Re: Polymorphic lists...
by oleg＠pobox.com 11 Mar '04

11 Mar '04

[Moving to Haskell-cafe from http://www.haskell.org/pipermail/glasgow-haskell-users/2004-March/006390.ht… http://www.haskell.org/pipermail/glasgow-haskell-users/2004-March/006393.ht… I hope y'all don't mind the move: the discussion of polymorphic lists is of general interest and is not limited to GHC. Besides, they serve coffee in here, albeit virtually. However, they charge for it virtually, too.] Keean Schupke wrote: > The list indexed by integers cannot determine the type of the > return value through induction on the class... in other words > it cannot determine the return type of the lookup function > until runtime: you can see this in the class instance for 'tke' > > > instance (TH a (a,b), TH W b) => TH W (a,b) where > > tke (W 0) th@(h,t) f = f h th > > tke (W n) (h,t) f = tke (W$ n-1) t f > > On the other hand indexing by natural numbers allows the compiler > to know the return type (and avoid the use of existentials) > because it is determined at compile time... you can see this because > the recursion termination is done by the type signatures in the instance > not the pattern guards of the function. > > instance Relation r => RIndex Zero (a `RCons` r) a where > rIndex Zero (x `RCons` _) = x > instance RIndex Idx r b => RIndex Idx (a `RCons` r) b where > rIndex (Suc n) (_ `RCons` xs) = rIndex n xs I concur wholeheartedly. I have expressed the same sentiment: http://www.haskell.org/pipermail/haskell/2003-August/012493.html http://www.haskell.org/pipermail/haskell/2003-June/011939.html The reason the previous message implemented indexing by true Int is because Ralf Laemmel specifically asked for it (plus it is much harder to do). Keean Schupke wrote: > It looks like most of this stuff has been done before... but I don't think > there is any of it in the ghc libraries. I needed this code for a real > application, and could not find anything suitable so I rolled my own. > > What do people think - is there a case for getting this stuff in the libs, > should we write a functional pearl? does anyone have any comments about > the code I posted, or how it could be improved? It is indeed a very good question. Just for the sake of it, here's a little bit simplified version of your example. Labels are done differently. > {-# OPTIONS -fglasgow-exts -fallow-undecidable-instances -fallow-overlapping-instances #-} > module Foo where > data Z = Z > data S a = S a > > class Nat a where n2n:: a-> Int > instance Nat Z where n2n _ = 0 > instance (Nat a) => Nat (S a) where n2n _ = 1 + n2n (undefined::a) > > -- keyed access > class (Nat n) => MLookup n a r where > mLookup :: r -> n -> a > instance MLookup Z a (a,r) where > mLookup r _ = fst r > instance MLookup n a r => MLookup (S n) a (a,r) where > mLookup (_,xs) _ = mLookup xs (undefined::n) > instance MLookup n a r => MLookup n a (b,r) where > mLookup (_,xs) n = mLookup xs n > > -- Positional access > class (Nat n) => MIndex n a r | n r -> a where > midx:: r -> n -> a > instance MIndex Z a (a,r) where midx (x,_) _ = x > instance (MIndex n a r) => MIndex (S n) a (b,r) where > midx (_,xs) _ = midx xs (undefined::n) The example now reads > newtype Name a = Name a deriving Show > newtype Size a = Size a deriving Show > newtype Weight a = Weight a deriving Show > > infixr 5 &+ > (&+) = (,) > test = (Name "Box") &+ (Size (3::Int)) &+ (Weight (1.1::Float)) > &+ (Name "AnotherBox") &+ (Size (42::Int)) &+ (Weight (24.09::Float)) > &+ () Note that at run-time, (Name "Box") is the same as "Box". Name is a compile-time-only label that incurs no run-time overhead. So, the essence is the same -- a polymorphic associative list where keys are ephemeral (have no run-time representation). "mLookup r n" finds the n-th association in this list of a type a. In the present representation, labels and values are specified together. There is no need for a type declaration for test. The compiler will figure it out. The name and the size of the first box *Foo> mLookup test Z::(Name String) Name "Box" *Foo> mLookup test Z::(Size Int) Size 3 and of the second one *Foo> mLookup test (S Z)::(Name String) Name "AnotherBox" *Foo> mLookup test (S Z)::(Size Int) Size 42 We can also access the element of the array by their absolute position: *Foo> midx test Z Name "Box" *Foo> midx test (S Z) Size 3 *Foo> midx test (S (S (S Z))) Name "AnotherBox" Decimal types for indices (rather than unary, as above) would make for a nicer interface. We can easily write a right fold > class MFoldr a r where > mfoldr :: (a -> b -> b) -> b -> r -> b > instance (MFoldr a r) => MFoldr a (a,r) where > mfoldr f z r = f (fst r) $ mfoldr f z (snd r) > instance MFoldr a () where > mfoldr f z r = z > instance MFoldr a r => MFoldr a (b,r) where > mfoldr f z r = mfoldr f z (snd r) and find out how many names are in our list *Foo> mfoldr (\ (Name (a::String)) n -> n + 1) 0 test 2 and the total sizes of our boxes *Foo> mfoldr (\ (Size s) a -> a + s) (0::Int) test 45 Incidentally, this polymorphic array may be a model of an extensible record with row polymorphism and even polymorphic labels. Yet another record proposal.

1 0

matching constructors
by Vadim Zaliva 09 Mar '04

09 Mar '04

Hi! I am new to Haskell, but I have background in various programming languages (including Lisp) I have very basic question, if there is a way to match algebraic types constructors besides use of pattern matching. I wrote today code like this: data Flag = Verbose | Input String | Output String | Filter String deriving Show instance Eq Flag where Verbose == Verbose = True Input _ == Input _ = True Output _ == Output _ = True Filter _ == Filter _ = True _ == _ = False findFlag :: Flag -> [Flag] -> Flag findFlag f [] = f findFlag y (x:xs) = if x == y then x else findFlag y xs If there is a cleaner way to implement findFlag and Eq Flag? Vadim -- "La perfection est atteinte non quand il ne reste rien a ajouter, mais quand il ne reste rien a enlever." (Antoine de Saint-Exupery)

5 8

HaRe import problem
by Georg Martius 08 Mar '04

08 Mar '04

Hi, I have a problem with Haskell Refactoring. I use the last snapshot from 26/02/2004 and emacs. If I have a source file with an import of a libary module e.g. Text.XML.HaXml.OneOfN I get: Source files missing for (add files with 'pfe add' or 'pfe chase'): Text.XML.HaXml.OneOfN, needed by Test Cheers, Georg

1 0

Haskell BDD library?
by Hans-Wolfgang Loidl 07 Mar '04

07 Mar '04

Hi, We are just starting on a project of parallelising a symbolic model checking algorithm, which operates on BDDs (binary-decision diagrams), in GpH. Does anyone have a Haskell implementation of such a library around and is willing to share it? Also, pointers to possibly useful BDD libraries, either in Haskell or lesser languages, would be welcome. Cheers, -- Hans-Wolfgang Loidl Ludwig-Maximilians-University Munich Tel: +49 89 / 2180 9864 Institut f. Informatik Fax: +49 89 / 2180 9338 Oettingenstr 67 Email: hwloidl(a)informatik.uni-muenchen.de D 80538 Munich URL: http://www.tcs.informatik.uni-muenchen.de/~hwloidl/

2 1