Re: [Haskell] Call for Contributions - HC&A Report (November 2006 edition)
Kurze Story zu BPL? ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
[Haskell] Call for participation: Workshop on Generic Programming 2006
Dear all,
the Workshop on Generic Programming early registration deadline is only a
few days away: August 18, 2006 (http://regmaster2.com/conf/icfp2006.html).
==> We have reserved 30 minutes for *lightning talks*. If you plan to
==> attend and if you would like to give a short talk (about half-baked,
==> exciting, new stuff) please drop me a short note. Slots will be
==> reserved on a first-come-first-serve basis.
Looking forward to seeing you in Portland, Ralf Hinze
CALL FOR PARTICIPATION
Workshop on Generic Programming 2006
Portland, Oregon, 16th September 2006
The Workshop on Generic Programming is sponsored by ACM SIGPLAN
and forms part of ICFP 2006. Previous Workshops on Generic
Programming have been held in Marstrand (affiliated with MPC),
Ponte de Lima (affiliated with MPC), Nottingham (informal
workshop), Dagstuhl (IFIP WG2.1 Working Conference), Oxford
(informal workshop), and Utrecht (informal workshop).
http://www.informatik.uni-bonn.de/~ralf/wgp2006.{html,pdf,ps,txt}
Preliminary program
---
9.oo - 1o.3o, session chair: Ralf Hinze (Universität Bonn)
Welcome
Design Patterns as Higher-Order Datatype-Generic Programs
Jeremy Gibbons (Oxford University)
Type Theoretic Design Patterns
Ondrej Rypacek, Roland Backhouse, Henrik Nilsson (University of Nottingham)
Generating Generic Functions
Johan Jeuring, Alexey Rodriguez, Gideon Smeding (Utrecht University)
11.oo - 12.3o, session chair: Peter Dybjer (Chalmers University of Technology)
Good Advice for Type-Directed Programming
Geoffrey Washburn, Stephanie Weirich (University of Pennsylvania)
Context-Parametric Polykinded Types
Pablo Nogueira (University of Nottingham)
Modular Generic Programming with Extensible Superclasses
Martin Sulzmann, Meng Wang (University of Singapore)
14.3o - 16.oo, session chair: Jeremy Gibbons (Oxford University)
Report from the program chair
Ralf Hinze (Universität Bonn)
Scrap++: Scrap Your Boilerplate in C++
Gustav Munkby, Andreas Priesnitz, Sibylle Schupp, Marcin Zalewski (Chalmers
University of Technology)
A Technique for Generic Iteration and Its Optimization
Stephen Watt (University of Western Ontario)
Lightning talks: to be announced
16.3o - 18.oo, session chair: Jeremy Siek (Rice University)
Towards An Automatic Complexity Analysis for Generic Programs
Kyle Ross (Indiana University)
An Object-Oriented Approach to Datatype Generic Programming
Adriaan Moors, Frank Piessen, Wouter Joosen (Katholieke Universiteit Leuven)
Discussion
___
Haskell mailing list
Haskell@haskell.org
http://www.haskell.org/mailman/listinfo/haskell
[Haskell] 2nd CFP: Workshop on Generic Programming 2006
[The deadline is approaching: 24 days left.]
SECOND CALL FOR PAPERS
Workshop on Generic Programming 2006
Portland, Oregon, 16th September 2006
The Workshop on Generic Programming is sponsored by ACM SIGPLAN
and forms part of ICFP 2006. Previous Workshops on Generic
Programming have been held in Marstrand (affiliated with MPC),
Ponte de Lima (affiliated with MPC), Nottingham (informal
workshop), Dagstuhl (IFIP WG2.1 Working Conference), Oxford
(informal workshop), and Utrecht (informal workshop).
http://www.informatik.uni-bonn.de/~ralf/wgp2006.{html,pdf,ps,txt}
Scope
-
Generic programming is about making programs more adaptable by making
them more general. Generic programs often embody non-traditional kinds
of polymorphism; ordinary programs are obtained from them by suitably
instantiating their parameters. In contrast with normal programs, the
parameters of a generic program are often quite rich in structure; for
example they may be other programs, types or type constructors, class
hierarchies, or even programming paradigms.
Generic programming techniques have always been of interest, both to
practitioners and to theoreticians, but only recently have generic
programming techniques become a specific focus of research in the
functional and object-oriented programming language communities. This
workshop will bring together leading researchers in generic
programming from around the world, and feature papers capturing the
state of the art in this important emerging area.
We welcome contributions on all aspects, theoretical as well as
practical, of
o adaptive object-oriented programming,
o aspect-oriented programming,
o component-based programming,
o generic programming,
o meta-programming,
o polytypic programming,
o and so on.
Submission details
--
Deadline for submission:3rd June 2006
Notification of acceptance:24th June 2006
Final submission due: 8th July 2006
Workshop: 16th September 2006
Authors should submit papers, in postscript or PDF format, formatted
for A4 paper, to Ralf Hinze ([EMAIL PROTECTED]) by 3rd June
2006. The length should be restricted to 12 pages in standard
(two-column, 9pt) ACM. Accepted papers are published by the ACM and
will additionally appear in the ACM digital library.
Programme committee
---
Roland Backhouse University of Nottingham
Pascal Costanza Vrije Universiteit Brussel
Peter Dybjer Chalmers University of Technology
Jeremy Gibbons University of Oxford
Johan JeuringUniversiteit Utrecht
Ralf Hinze (chair) Universität Bonn
Karl Lieberherr Northeastern University
David Musser Rensselaer Polytechnic Institute
Rinus Plasmeijer Universiteit Nijmegen
Sibylle Schupp Chalmers University of Technology
Jeremy Siek Rice University
Don Syme Microsoft Research
___
Haskell mailing list
Haskell@haskell.org
http://www.haskell.org/mailman/listinfo/haskell
[Haskell] CFP: Workshop on Generic Programming 2006
CALL FOR PAPERS
Workshop on Generic Programming 2006
Portland, Oregon, 16th September 2006
The Workshop on Generic Programming is sponsored by ACM SIGPLAN
and forms part of ICFP 2006. Previous Workshops on Generic
Programming have been held in Marstrand (affiliated with MPC),
Ponte de Lima (affiliated with MPC), Nottingham (informal
workshop), Dagstuhl (IFIP WG2.1 Working Conference), Oxford
(informal workshop), and Utrecht (informal workshop).
http://www.informatik.uni-bonn.de/~ralf/wgp2006.{html,pdf,ps,txt}
Scope
-
Generic programming is about making programs more adaptable by making
them more general. Generic programs often embody non-traditional kinds
of polymorphism; ordinary programs are obtained from them by suitably
instantiating their parameters. In contrast with normal programs, the
parameters of a generic program are often quite rich in structure; for
example they may be other programs, types or type constructors, class
hierarchies, or even programming paradigms.
Generic programming techniques have always been of interest, both to
practitioners and to theoreticians, but only recently have generic
programming techniques become a specific focus of research in the
functional and object-oriented programming language communities. This
workshop will bring together leading researchers in generic
programming from around the world, and feature papers capturing the
state of the art in this important emerging area.
We welcome contributions on all aspects, theoretical as well as
practical, of
o adaptive object-oriented programming,
o aspect-oriented programming,
o component-based programming,
o generic programming,
o meta-programming,
o polytypic programming,
o and so on.
Submission details
--
Deadline for submission:3rd June 2006
Notification of acceptance:24th June 2006
Final submission due: 8th July 2006
Workshop: 16th September 2006
Authors should submit papers, in postscript or PDF format, formatted
for A4 paper, to Ralf Hinze ([EMAIL PROTECTED]) by 3rd June
2006. The length should be restricted to 12 pages in standard
(two-column, 9pt) ACM. Accepted papers are published by the ACM and
will additionally appear in the ACM digital library.
Programme committee
---
Roland Backhouse University of Nottingham
Pascal Costanza Vrije Universiteit Brussel
Peter Dybjer Chalmers University of Technology
Jeremy Gibbons University of Oxford
Johan JeuringUniversiteit Utrecht
Ralf Hinze (chair) Universität Bonn
Karl Lieberherr Northeastern University
David Musser Rensselaer Polytechnic Institute
Rinus Plasmeijer Universiteit Nijmegen
Sibylle Schupp Chalmers University of Technology
Jeremy Siek Rice University
Don Syme Microsoft Research
___
Haskell mailing list
Haskell@haskell.org
http://www.haskell.org/mailman/listinfo/haskell
[Haskell] ANNOUNCE: Frown - an LALR(k) Parser Generator for Haskell (version 0.6, beta)
I'm pleased to announce the first release of Frown (version 0.6, andromeda release), an LALR(k) Parser Generator for Haskell 98. This is a beta quality release. Frown's salient features are: o The generated parsers are time and space efficient. On the downside, the parsers are quite large. o Frown generates four different types of parsers. As a common characteristic, the parsers are genuinely functional (ie `table-free'); the states of the underlying LR automaton are encoded as mutually recursive functions. Three output formats use a typed stack representation, one format due to Ross Paterson (code=stackless) works even without a stack. o Encoding states as functions means that each state can be treated individually as opposed to a table driven-approach, which necessitates a uniform treatment of states. For instance, look-ahead is only used when necessary to resolve conflicts. o Frown comes with debugging and tracing facilities; the standard output format due to Doaitse Swierstra (code=standard) may be useful for teaching LR parsing. o Common grammatical patterns such as repetition of symbols can be captured using rule schemata. There are several predefined rule schemata. o Terminal symbols are arbitrary variable-free Haskell patterns or guards. Both terminal and nonterminal symbols may have an arbitrary number of synthesized attributes. o Frown comes with extensive documentation; several example grammars are included. Furthermore, Frown supports the use of monadic lexers, monadic semantic actions, precedences and associativity, the generation of backtracking parsers, multiple start symbols, error reporting and a weak form of error correction. Frown is available in source form, which can be compiled with GHC version 5.02+. The source code and further information is available on the Frown home page http://www.informatik.uni-bonn.de/~ralf/frown/index.html Please send any bug reports and comments to [EMAIL PROTECTED] Happy frowning, Ralf ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell] translation of "kind"
Am Montag, 20. Juni 2005 13:45 schrieb Christian Maeder: > you could also say "ein Typkonstruktor mit Kind ..." (and leave the > gender open) Hier ist er: , _/^\_ < > /.-.\ `/&\` ,@.*;@, /_o.I %_\ (`'--:o(_@; /`;--.,__ `') ;@`o % O,*`'`&\ (`'--)_@ ;o %'()\ ,==. /`;--._`''--._O'@; / 66\ /&*,()~o`;-.,_ `""`) \c -_) /`,@ ;+& () o*`;-';\ `) ( (`""--.,_0 +% @' &()\ / \ /-.,_``''---'`) / \ \ /@%;o`:;'--,.__ __.'\ (( /\ \_ ;*,&(); @ % &^;~`"`o;@(); \\ \ `--` /(); o^~; & ()[EMAIL PROTECTED]&`;&%O\ / / / `"="==""==,,,.,="=="==="` (_(___) # .. der Tpykonstruktor `Tree' mit Kind ... ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell] translation of "kind"
Am Montag, 20. Juni 2005 12:06 schrieb Christian Maeder: > Even Peter Thiemann in "Grundlagen der funktionalen Programmierung" > (1994) did not translate "Kind", although he used "geschönfinkelt" for > "curry" (honoring logicians Schönfinkel and Curry) > > I'ld prefer "der Kind" (and avoid situtations that allowed confusion > with "das Kind") Honestly, this is truly horrible (sorry, Peter). Just try to read it aloud: "der Kind des Typkonstruktors ...". ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell] translation of "kind"
> can anybody tell me what the German translation of the word "kind" as used in > type theory and especially in Haskell is? Wie wär's mit `Sorte', Ralf ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: 'Forest inversion'?
Dear Marnix,
your transformation can be rewritten as the composition of three
functions: one that converts the forest into a binary tree (this
is based on the natural correspondence between forests and binary
trees (*), see Knuth TAOCP, Vol 1), one that mirrors a binary tree
swapping left and right subtrees, and one that transforms the
resulting binary tree back into a forest. Each of these transformations
is quite well-known, but alas I know of no name for the composition.
Cheers, Ralf
(*) The binary tree representation of forest is sometimes called
left-child, right-sibling representation. But you probably already
know that.
> Recently I've discovered an inversion operation on forests that transforms
> 'wide' forests into 'deep' onces and vice versa. I'm sure that this
> operation is already known, however, I could not find any information on
> it. (Largely because I don't know under what name to look for it.) You
> Haskell guys know about data structures, so you should know more. :-)
>
> Example (use a fixed with font to view): the single-tree forest
>
> A
> /|\
> B C D
>
> | | |\
>
> E F G H
>
> I J
>
> K
>
> is inverted to the forest
>
> A BE
> /| |\
> C F I K
>/ \
> D G
> / \
> H J
>
> and vice versa.
>
> In an implementation where every node has two pointers, one to its first
> child and one to its right-hand sibling, the inversion means that in every
> node those two pointers are swapped.
>
> In Haskell the algorithm looks like this:
> > data Forest a = Forest {trees :: [(a, Forest a)]} deriving (Show, Eq)
> >
> > inv :: Forest a -> Forest a
> > inv (Forest []) = Forest []
> > inv (Forest ((a,f) : g)) = Forest ((a, inv (Forest g)) : trees (inv f))
>
> and it is easy to prove that for every f :: Forest a, inv (inv f) = f.
>
> What would I want to do with it? Well, deep trees are difficult to
> navigate using existing tree controls. Example: Suppose I want to let the
> user play a text adventure, but I allow 'undo'. Then I can show him the
> tree of moves that he already tried, and let him backup to a previous
> state, and try something else at that point. This results often in a deep
> tree. So showing a wide tree instead (using the above inversion) might
> help the user. Especially if the children of a node are 'ordered' in the
> sense that the first child node is most important.
>
> So: is this 'forest inversion' known, under which name, what are the known
> uses, etc.?
>
> Thanks in advance!
>
> Groetjes,
> <><
> Marnix
> --
> Marnix Klooster
> [EMAIL PROTECTED]
> ___
> Haskell mailing list
> [EMAIL PROTECTED]
> http://www.haskell.org/mailman/listinfo/haskell
___
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
Re: Language extension proposal
> If we could only figure out a good syntax for > (optional) type application, it would deal rather nicely with many of > these cases. Trouble is, '<..>' gets confused with comparisons. And > when there are multiple foralls, it's not obvious what order to supply > the type parameters. What about mantissa (| Double |) + 4 ? Order: left to right as they appear in the quantifier or else (more heavy-weight) several special brackets (curried foralls) ... sequence (| \ b . ST b MyState |) (| Int |) ... So we can write ... sequence ...all foralls are implicit ... sequence (| \ b . ST b MyState |) ... the second forall is implicit but not ... sequence (| Int |) ... the first forall is implicit Cheers, Ralf ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Typesafe MRef with a regular monad
> Yes, that's a good point. So there are really three issues: > a) single-threaded-ness > b) making sure you look up in the right map > c) making sure the thing you find has the right type > > Even if you have typed keys, (Key a), then if you look them up in the > wrong map, any guarantee that it maps to a value of type 'a' is out of > the window. Not true, if you use the finite map implementation based on dynamics. Here, the story is: with single-threaded-ness you can omit the dynamic type checks (they are guaranteed to succeed); if you use finite maps in a persistent manner, this is no longer true. Cheers, Ralf ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Typesafe MRef's
Am Freitag, 13. Juni 2003 17:12 schrieb George Russell: > Keith wrote (snipped) > > > But George Russell's implementation relied on looking up something in > > one map with a key obtained from another map. I thought type-safe > > MRefs should disallow this. > > However if you disallow lookup up in one map with a key from another, > then Ralf Hinze's solution of putting the value inside the key > uses no type extentions and works perfectly well (though is probably > not quite what was intended). Here is the modified version of `update': update :: (Typable b) => FM k -> Key k a -> a -> FM k update (FM bs) (Key k r) b = FM ((k, Dyn r b) : bs) ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Typesafe MRef with a regular monad
Am Freitag, 6. Juni 2003 16:09 schrieb Simon Peyton-Jones: > You can't overwrite an entry with a value of a different type, because > the keys are typed! Any more than you can overwrite an IORef with a > value of a different type. > S Why is that? Ok, here is my second implementation. It uses the Dynamic module from our HW2002 paper. A key is a pair consisting of the actual key and a type representation. > module TypedFM > where > import Prelude hiding (lookup) > import qualified Prelude > import Dynamics > data FM k = FM [(k, Dynamic)] > data Key k a = Key k (Type a) > empty :: FM k > empty = FM [] > insert:: (Typable a) => FM k -> k -> a -> (FM k, Key k a) > insert (FM bs) k a= (FM ((k, Dyn rep a) : bs), Key k rep) > lookup:: (Eq k) => FM k -> Key k a -> Maybe a > lookup (FM bs) (Key k rep)= case Prelude.lookup k bs of > Nothing -> Nothing > Just dy -> cast dy rep > update:: (Typable b) => FM k -> Key k a -> b -> (FM k, Key k > b) > update (FM bs) (Key k _) b= (FM ((k, Dyn rep b) : bs), Key k rep) Does this fit the bill? Cheers, Ralf ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Typesafe MRef with a regular monad
Am Freitag, 6. Juni 2003 15:47 schrieb Simon Peyton-Jones: > Yes, one *could* use dynamic types. But the check would always succeed! Why is that? If I overwrite an entry with a value of a different type, then the check fails. I am certainly missing something ... Cheers, Ralf ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Typesafe MRef with a regular monad
Am Freitag, 6. Juni 2003 15:23 schrieb Simon Peyton-Jones: > Oh bother, I forgot to add that you can of course insert a new value > with an old key (suitably typed) and have it overwrite. Else, as you > say, there would not be much point. > > Maybe it'd be better to have a separate key-construction function > newKey :: k -> Key k a > instead of having insert return a key. > > S Seriously, isn't this just an application of dynamics? The key type allows us to insert a cast when looking up a data structure of dynamic values? Cheers, Ralf ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Typesafe MRef with a regular monad
> A more concrete way to formulate a problem that I believe to be > equivalent is this. Implement the following interface > >module TypedFM where > data FM k -- Abstract; finite map indexed by keys > of type k > data Key k a-- Abstract; a key of type k, indexing a > value of type a > > empty :: FM k > insert :: Ord k => FM k -> k -> a -> (FM k, Key k a) > lookup :: Ord k => FM k -> Key k a -> Maybe a > > The point is that the keys are typed, like Refs are. But the finite map > FM is only parameterised on k, not a, so it can contain (key,value) > pairs of many different types. > > I don't think this can be implemented in Haskell, even with > existentials. But the interface above is completely well typed, and can > be used to implement lots of things. What I *don't* like about it is > that it embodies the finite-map implementation, and there are too many > different kinds of finite maps. Here is a Haskell 98 implementation: > module TypedFM > where > data FM k = FM > data Key k a = Key k a > empty = FM > insert FM k a = (FM, Key k a) > lookup FM (Key k a) = Just a Cheers, Ralf ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: ANN: H98 FFI Addendum 1.0, Release Candidate 10
> On Fri, Jun 06, 2003 at 09:32:18AM +0100, Simon Peyton-Jones wrote: > > Yes! Yes! Advice is good! > > OK, how about "avoid unsafePerformIO like the plague"? > > Why is it the business of the FFI spec to document unsafe uses of > unsafePerformIO? I'd like to second Ross here. Advice is good at the right place at the right time. Cheers, Ralf ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: forall quantifier
Am Freitag, 6. Juni 2003 09:15 schrieb Simon Peyton-Jones: > I forget whether I've aired this on the list, but I'm seriously thinking > that we should change 'forall' to 'exists' in existential data constructors > like this one. One has to explain 'forall' every time. But we'd lose a > keyword. Or omit the keyword altogether (Doaitse has suggested this before). This is quite in line with uses of quantifiers elsewhere (in the horn rule `path(A,C) :- path(A,B), path(B, C)' the variable `C' is implicitly existentially quantified in the body). Cheers, Ralf ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Collecting values from Functors?
> Rather than using fmap, why not use gmap in GHC. > Using an appropriate generic traversal scheme, > say listify, all the code you write is the > following expression: > > listify (const True) mytree :: [Int] > > if you are looking for all the Ints in > mytree = Fork (Leaf 42) (Fork (Leaf 88) (Leaf 37)) > So this would give you [42,88,37]. What happens if the tree contains additional integers to record, say, balancing information. The information a functor provides is vital here. Take as the simplest example newtype Weighted a = WithWeight (Int, a) Without the functor definition there is no way to distinguish the two Ints in Weighted Int. Cheers, Ralf ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Random Permutations
> Is there a library routine for random permutations?
>
> I didn't find any and did a quick hack, which works fine for my
> application (length of list < 100), but what would be a more
> elegant way?
>
> > permute :: StdGen -> [a] -> [a]
> > permute gen [] = []
> > permute gen xs = (head tl) : permute gen' (hd ++ tail tl)
> >where (idx, gen') = randomR (0,length xs - 1) gen
> > (hd, tl) = splitAt idx xs
I've attached some *old* code that generates a random permutation.
Hope it still works ...
Cheers, Ralf
%---=
\section{Generate a random permutation}
%---=
> module RandomPerm(
> randomPerm, randomPerms)
> where
> import Random
> import Int
> import Array
> import ST
% - - - - - - - - - - - - - - - = - - - - - - - - - - - - - - - - - - - - - - -
\subsection{Signature}
% - - - - - - - - - - - - - - - = - - - - - - - - - - - - - - - - - - - - - - -
> randomPerm:: (RandomGen g) => [a] -> g -> ([a], g)
> randomPerms :: (RandomGen g) => [a] -> g -> [[a]]
% - - - - - - - - - - - - - - - = - - - - - - - - - - - - - - - - - - - - - - -
\subsection{Implementation}
% - - - - - - - - - - - - - - - = - - - - - - - - - - - - - - - - - - - - - - -
For a list of length |n| we calculate a random number between |0| and
|n! - 1|. This random number is converted to the factorial number
system, see \cite[p.66]{Knu97Art2}. Recall that in this system a
sequence of `digits' $b_{n-1}\ldots b_0$ with $0 \leq b_i \leq i$
denotes the number $\sum_{i} b_i\cdot i!$ (note that $b_0$ is
necessarily $0$). This sequence is then used as a recipe for building
a random permutation: we exchange the elements at positions $i$ and
$i + b_i$ for $0 \leq i < n$.
> randomPerm as g = (permute num as, g')
> where (num, g') = generate (length as) g
> randomPerms as g = as' : randomPerms as g'
> where (as', g') = randomPerm as g
Generates a random number between |0| and |n! - 1| in the `factorial'
number system representation.
> generate :: (RandomGen g) => Int -> g -> ([Int], g)
> generate n g = (convert fs r, g')
> where (f : fs)= reverse (take (n + 1) (factorials 0 1))
> (r, g') = randomR (0, f - 1) g
Convert a number to a mixed-radix numeral (the radices are given as the
first argument).
> convert :: [Integer] -> Integer -> [Int]
> convert [] _n = [] -- |_n| should be |0|
> convert (f : fs) n= toInt q : convert fs r
> where (q, r) = divMod n f
The list of factorial numbers.
> factorials:: Int -> Integer -> [Integer]
> factorials i f= f : factorials (i + 1) (f * fromInt (i + 1))
Note that we have to call |factorial i f| such that |f| is |i!|.
The function |permute| permutes the given list according to the
`factorial' numeral.
> permute :: [Int] -> [a] -> [a]
> permute num as= runST (
>do { a <- newSTArray bs undefined;
> sequence_ [
> writeSTArray a i e
> | (i, e) <- zip is as ];
> sequence [
> swap a i (i + r)
> | (i, r) <- zip is num ];
> mapM (readSTArray a) is })
> where bs = (0, length as - 1)
> is = range bs
The operation |swap| exchanges two elements of a mutable array.
> swap :: (Ix ix) => STArray s ix a -> ix -> ix -> ST s ()
> swap a i j= do { x <- readSTArray a i;
> y <- readSTArray a j;
> writeSTArray a i y;
> writeSTArray a j x }
___
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
HR, App. D.5, minor correction
Hi Simon, here is a minor correction to the May version of the HR. In appendix D.5 there is a table with an example for derived instances: for reasons of consistency the line showsPrec d (Leaf m) = showParen (d >= 10) showStr should be replaced by showsPrec d (Leaf m) = showParen (d > app_prec) showStr Cheers, Ralf ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: [ADMINISTRIVIA]: Change list submission policy please?
> The haskell mailing list is getting an increasing amount of > spam, viruses, and virus warnings. Would it be possible > to change the list policy to only allow submissions from > subscribed members? Please? I'd like to second this. The amount of spam etc is becoming more and more annoying ... Cheers, Ralf ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
WAAAPL 2002, final call for papers
Apologies if you receive multiple copies...
FINAL CALL FOR PAPERS
ACM SIGPLAN
WAAAPL 2002
[Deadline for submission: 3rd June 2002]
Workshop on
Algorithmic Aspects of Advanced Programming Languages
Part of PLI'02
Pittsburgh, PA, USA
Monday, October 7
http://www.cs.uni-bonn.de/~ralf/waaapl02.{html,pdf,ps,dvi,txt}
Scope
-
WAAAPL (pronounced "wapple") seeks papers on all aspects of the
design, analysis, evaluation, or synthesis of algorithms or data
structures in the context of advanced programming languages, such as
functional or logic languages, where traditional algorithms or data
structures may be awkward or impossible to apply. Possible topics
include (but are not limited to):
o new algorithms or data structures,
o empirical studies of existing algorithms or data structures,
o new techniques or frameworks for the design, analysis,
evaluation, or synthesis of algorithms or data structures,
o applications or case studies,
o pedagogical issues (language aspects of teaching algorithms or
algorithmic aspects of teaching languages).
A previous WAAAPL workshop has been held in Paris (1999).
Submission details
--
Deadline for submission:3rd June 2002
Notification of acceptance: 1st July 2002
Final submission due: 1st August 2002
WAAAPL Workshop:7th October 2002
Authors should submit papers of at most 12 pages, in postscript
format, formatted for A4 paper, to Ralf Hinze ([EMAIL PROTECTED]) or
Chris Okasaki ([EMAIL PROTECTED]) by 3rd June 2002. The
proceedings will be published by ACM and will appear in the ACM
digital library.
Programme committee
---
Richard Bird Oxford University
Michael Hanus University of Kiel
Ralf HinzeUniversity of Bonn (co-chair)
Zhenjiang Hu University of Tokyo
Haim Kaplan Tel Aviv University
Chris Okasaki United States Military Academy (co-chair)
Melissa O'Neill Harvey Mudd College
___
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
Syntax highlighting for KDE's Kate
Dear KDE users, I've hacked syntax highlighting files for Kate, KDE's editor. Feel free to use or to modify them. http://www.informatik.uni-bonn.de/~ralf/software.html#syntax Cheers, Ralf ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
CFP: JFP Special Issue on Functional Pearls
Apologies if you receive multiple copies... CALL FOR PAPERS Special Issue on Functional Pearls http://www.informatik.uni-bonn.de/~ralf/necklace.html [Deadline: 31 August 2002] Wer die Perle in Händen hält, fragt nicht nach der Muschel. - Peter Benary A special issue of the Journal of Functional Programming will be devoted to Functional Pearls. The submission deadline is 31 August 2002. Scope - Do you have a paper that is small, rounded and enjoyable to read? Please consider submitting it to the Special Issue on Functional Pearls, as we intend to string a shiny necklace. If you don't have a pearl, write one today! Papers can be on any subject connected to functional programming. A pearl is typically around 8 pages, though there is no strict page limit. The special issue also welcomes tutorial or educational papers in a broad sense. Submission details -- Manuscripts should be unpublished works and not submitted elsewhere. Revised and polished versions of papers published in conference proceedings that have not appeared in archival journals are eligible for submission. All submissions will be reviewed according to the usual standards of scholarship and judged by elegance of development and clarity of expression. One of the main reviewers will be Richard Bird, the editor of JFP's regular Functional Pearls column. Deadline for submission: 31 August 2002 Notification of acceptance or rejection: 30 November 2002 Revised version due: 31 January 2003 Submissions should be sent to the Guest Editor (see address below), with a copy to Nasreen Ahmad ([EMAIL PROTECTED]). Submitted articles should be sent in PDF or Postscript format, preferably gzipped and uuencoded. The use of the JFP style files is strongly recommended. In addition, please send, as plain text, title, abstract (if any), and contact information. The submission deadline is 31 August 2002. Authors will be notified of acceptance or rejection by 30 November 2002. Revised versions are due on 31 January 2003. 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 -------- Ralf Hinze Institut für Informatik III Universität Bonn Römerstraße 164 53117 Bonn, Germany Telephone: +49 (2 28) 73 - 45 35 Fax: +49 (2 28) 73 - 43 82 Email: [EMAIL PROTECTED] WWW: http://www.informatik.uni-bonn.de/~ralf/ ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Haskell Report: minor error
Hi Simon, minor error in the Report: Figure 5 that displays the hierarchy of Haskell classes defined in the Prelude also includes the MonadPlus class, which, however, is defined in Monad. Cheers, Ralf ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: does this have a name (recusive datatypes)
> Does this have a name: > > data S s a = Nil | S a (s (S s a)) I sometimes use the name `generalized rose tree' but that's certainly not standard. Chris Okasaki uses this data type, for instance, to implements priority queues with an efficient merge, see his book `Purely functional data structures'. > Is there any theory about what types of recursive data structures can be > captured with "S" and what types cannot? It seems that those > datastructures which are isomorphic to S x for some x (satisfying certain > properties) are exactly those on which one can apply things like maps, > filters and folds. Not true. Binary leaf trees cannot be captured as `S' always has a label in the internal nodes: data LTree a = Leaf a | Fork (LTree a) (LTree a) Note that you can define maps for virtually every data type (if we ignore function spaces), see the paper `Polytypic values possess polykinded types': http://www.informatik.uni-bonn.de/~ralf/publications.html#J9 > Also, if we want to write a show instance for S s, this seems to be > impossible. Is it? If so, is this a weakness in Haskell (cyclic instance > declarations) or is it theoretically not possible? You need higher-order contexts, see Section 7 of the `Derivable type classes' paper http://www.informatik.uni-bonn.de/~ralf/publications.html#P13 Cheers, Ralf ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
GHC 5.02.3, SuSE rpms
I've uploaded SuSE 7.3 rpms for the patchlevel release of the Glasgow Haskell Compiler (GHC), version 5.02.3. http://www.informatik.uni-bonn.de/~ralf/ghc-5.02.3-1.src.rpm http://www.informatik.uni-bonn.de/~ralf/ghc-5.02.3-1.i386.rpm http://www.informatik.uni-bonn.de/~ralf/ghc-prof-5.02.3-1.i386.rpm Enjoy, Ralf ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
WAAAPL 2002, preliminary announcement
Apologies if you receive multiple copies...
PRELIMINARY CALL FOR PAPERS
[Deadline for submission: 3rd June 2002]
WAAAPL 2002
Workshop on
Algorithmic Aspects of Advanced Programming Languages
Part of PLI'02 (approval pending)
Pittsburgh, PA, USA
date to be announced (probably Oct 7 or Oct 8, 2002)
http://www.cs.uni-bonn.de/~ralf/waaapl02.{html,pdf,ps,dvi,txt}
Scope
-
WAAAPL (pronounced "wapple") seeks papers on all aspects of the
design, analysis, evaluation, or synthesis of algorithms or data
structures in the context of advanced programming languages, such as
functional or logic languages, where traditional algorithms or data
structures may be awkward or impossible to apply. Possible topics
include (but are not limited to):
o new algorithms or data structures,
o empirical studies of existing algorithms or data structures,
o new techniques or frameworks for the design, analysis,
evaluation, or synthesis of algorithms or data structures,
o applications or case studies,
o pedagogical issues (language aspects of teaching algorithms or
algorithmic aspects of teaching languages).
A previous WAAAPL workshop has been held in Paris (1999).
Submission details
--
Deadline for submission:3rd June 2002
Notification of acceptance: 1st July 2002
Final submission due: 1st August 2002
WAAAPL Workshop:to be announced (probably Oct 7 or Oct 8, 2002)
Authors should submit papers of at most 12 pages, in postscript
format, formatted for A4 paper, to Ralf Hinze ([EMAIL PROTECTED]) or
Chris Okasaki ([EMAIL PROTECTED]) by 3rd June 2002. The
accepted papers will be published as a University of Bonn technical
report.
Programme committee
---
Richard Bird Oxford University
Michael Hanus University of Kiel
Ralf HinzeUniversity of Bonn (co-chair)
Zhenjiang Hu University of Tokyo
Haim Kaplan Tel Aviv University
Chris Okasaki United States Military Academy (co-chair)
Melissa O'Neill Harvey Mudd College
___
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
Haskell workshop: 10-minute slots
Folks, The Haskell Workshop in Firenze on 2nd September is now only a couple of weeks away. If you'd like to attend but haven't yet registered, please do so as soon as possible. For further details, see: http://music.dsi.unifi.it/pli01/registration/index.html The workshop programme is available here (including the proceedings): http://www.cs.uu.nl/~ralf/hw2001.html In addition to longer presentations on accepted papers, a number of slots for participants to make 10-minute informal presentations are available. If you'd like to request such a slot, please drop me an email. Note: the talk need not be polished, the wackier the better. Cheers, Ralf ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
2001 Haskell Workshop: call for participation
CALL FOR PARTICIPATION
ACM SIGPLAN
2001 Haskell Workshop
Firenze, Italy, 2nd September 2001
The Haskell Workshop is sponsored by ACM SIGPLAN and forms
part of the PLI 2001 colloquium on Principles, Logics, and
Implementations of high-level programming languages, which
comprises the ICFP/PPDP conferences and associated workshops.
Previous Haskell Workshops have been held in La Jolla (1995),
Amsterdam (1997), Paris (1999), and Montreal (2000).
http://www.cs.uu.nl/~ralf/hw2001.{html,pdf,ps,txt}
Workshop programme
--
The workshop received a total of 23 submissions and after careful
consideration the programme committee selected the 10 papers below
(6 regular, 4 pearls, and no application letters) for acceptance. The
selection was competitive: several good papers had to be rejected.
Please, note that in addition to longer presentations on accepted
papers, a number of slots for participants to make 10-minute informal
presentations are available. To request such a slot, contact Ralf
Hinze ([EMAIL PROTECTED]).
9.00 - 10.30: chaired by Ralf Hinze
Functional Pearl: "Derivation of a Carry Lookahead Addition Circuit",
John O'Donnell and Gudula R?nger
Functional Pearl: "Inverting the Burrows-Wheeler Transform",
Richard Bird, Shin-Cheng Mu, and Barney Stratford
"Genuinely Functional User Interfaces",
Antony Courtney and Conal Elliott
10.30 - 11.00:
Coffee break
11.00 - 12.30: chaired by Patrik Jansson
"Named Instances for Haskell Type Classes",
Wolfram Kahl and Jan Scheffczyk
"A Functional Notation for Functional Dependencies",
Martin Gasbichler, Matthias Neubauer, Michael Sperber, and Peter Thiemann
Report from the program chair and 10-minute talks (to be announced)
12.30 - 14.00:
Lunch
14.00 - 15.30: chaired by Ross Paterson
"GHood - Graphical Visualisation and Animation of Haskell Object Observations",
Claus Reinke
"Multiple-View Tracing for Haskell: a New Hat",
Malcolm Wallace, Olaf Chitil, Thorsten Brehm, and Colin Runciman
10-minute talks (to be announced)
15.30 - 16.00:
Coffee break
16.00 - 17.30: chaired by Jeremy Gibbons
Functional Pearl: "Parsing Permutation Phrases",
Arthur Baars, Andres L?h, and S. Doaitse Swierstra
Functional Pearl: "Pretty Printing with Lazy Dequeues",
Olaf Chitil
"Playing by the Rules: Rewriting as a practical optimisation technique in GHC",
Simon Peyton Jones, Andrew Tolmach, and Tony Hoare
17.30 - 18.00: chaired by Manuel Chakravarty
Discussion: the future of Haskell
Programme committee
---
Manuel Chakravarty University of New South Wales
Jeremy Gibbons University of Oxford
Ralf Hinze (chair) University of Utrecht
Patrik Jansson Chalmers University
Mark Jones Oregon Graduate Institute
Ross Paterson City University, London
Simon Peyton Jones Microsoft Research
Stephanie Weirich Cornell University
Scope
-
The purpose of the Haskell Workshop is to discuss experience with
Haskell, and possible future developments for the language. The scope
of the workshop includes all aspects of the design, semantics, theory,
application, implementation, and teaching of Haskell. Submissions that
discuss limitations of Haskell at present and/or propose new ideas for
future versions of Haskell are particularly encouraged. Adopting an
idea from ICFP 2000, the workshop also solicits two special classes of
submissions, application letters and functional pearls, described
below.
Application Letters
---
An application letter describes experience using Haskell to solve
real-world problems. Such a paper might typically be about six pages,
and may be judged by interest of the application and novel use of
Haskell.
Functional Pearls
-
A functional pearl presents - using Haskell as a vehicle - an idea that
is small, rounded, and glows with its own light. Such a paper might
typically be about six pages, and may be judged by elegance of
development and clarity of expression.
Useful links
PLI 2001http://music.dsi.unifi.it/pli01/
H
Re: Eq instance for (a,b,c,d,e) and upwards
Henrik Nilsson wrote: > So, if, in the interest of being conservative, the stated minimal > bound cannot be "infinity", could it at least be a great deal > bigger than what reasonably would be used in *hand-written* > code? Say 15. An arbitrary choice, of course, but it is not > excessive from an implementation perspective, yet large enough > that I cannot imagine hand-written code getting close to the > limit. I second Henrik here, 15 is much better than 7. Cheers, Ralf ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Permutations of a list
Andy Fugard wrote: > My main question is really what facilities of the language I should be > looking at to make this code more elegant! As you can see I currently know > only the basics of currying, and some list operations. Definitely list comprehensions! I digged out some old code: > module Perms where Permutations. > perms :: [a] -> [[a]] > perms [] = [ [] ] > perms (a : x) = [ z | y <- perms x, z <- insertions a y ] > > insertions:: a -> [a] -> [[a]] > insertions a [] = [ [a] ] > insertions a x@(b : y)= (a : x) : [ b : z | z <- insertions a y ] Using deletions instead of insertions; generates the permutations in lexicographic order, but is a bit slower. > perms':: [a] -> [[a]] > perms' [] = [ [] ] > perms' x = [ a : z | (a, y) <- deletions x, z <- perms' y ] > deletions :: [a] -> [(a, [a])] > deletions [] = [] > deletions (a : x) = (a, x) : [ (b, a : y) | (b, y) <- deletions x ] Cheers, Ralf ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
2001 Haskell Workshop: final call for papers
FINAL CALL FOR PAPERS
[Deadline for submission: 1st June 2001]
2001 Haskell Workshop
Firenze, Italy, 2nd September 2001
The Haskell Workshop forms part of the PLI 2001 colloquium
on Principles, Logics, and Implementations of high-level
programming languages, which comprises the ICFP/PPDP conferences
and associated workshops. Previous Haskell Workshops have been
held in La Jolla (1995), Amsterdam (1997), Paris (1999), and
Montreal (2000).
http://www.cs.uu.nl/people/ralf/hw2001.{html,pdf,ps,txt}
Scope
-
The purpose of the Haskell Workshop is to discuss experience with
Haskell, and possible future developments for the language. The scope
of the workshop includes all aspects of the design, semantics, theory,
application, implementation, and teaching of Haskell. Submissions that
discuss limitations of Haskell at present and/or propose new ideas for
future versions of Haskell are particularly encouraged. Adopting an
idea from ICFP 2000, the workshop also solicits two special classes of
submissions, application letters and functional pearls, described
below.
Application Letters
---
An application letter describes experience using Haskell to solve
real-world problems. Such a paper might typically be about six pages,
and may be judged by interest of the application and novel use of
Haskell.
Functional Pearls
-
A functional pearl presents - using Haskell as a vehicle - an idea that
is small, rounded, and glows with its own light. Such a paper might
typically be about six pages, and may be judged by elegance of
development and clarity of expression.
Submission details
--
Deadline for submission:1st June 2001
Notification of acceptance: 12th July 2001
Final submission due: 1st August 2001
Haskell Workshop: 2nd September 2001
Authors should submit papers in postscript format, formatted for A4
paper, to Ralf Hinze ([EMAIL PROTECTED]) by 1st June 2001. Use of the
ENTCS style files is strongly recommended. The length should be
restricted to the equivalent of 5000 words (which is approximately 24
pages in ENTCS format, or 12 pages in ACM format). Note that this
word limit represents a change from the first call for papers.
Application letters and functional pearls should be labeled as such on
the first page; they may be any length up to the above limit, though
shorter submissions are welcome. The accepted papers will initially
appear as a University of Utrecht technical report, and subsequently
be published as an issue of Electronic Notes in Theoretical Computer
Science.
Programme committee
---
Manuel Chakravarty University of New South Wales
Jeremy Gibbons University of Oxford
Ralf Hinze (chair) University of Utrecht
Patrik Jansson Chalmers University
Mark Jones Oregon Graduate Institute
Ross Paterson City University, London
Simon Peyton Jones Microsoft Research
Stephanie Weirich Cornell University
___
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
2001 Haskell Workshop: 1st call for papers
FIRST CALL FOR PAPERS
[Deadline for submission: 1st June 2001]
2001 Haskell Workshop
Firenze, Italy, 2nd September 2001
The Haskell Workshop forms part of the PLI 2001 colloquium
on Principles, Logics, and Implementations of high-level
programming languages, which comprises the ICFP/PPDP conferences
and associated workshops. Previous Haskell Workshops have been
held in La Jolla (1995), Amsterdam (1997), Paris (1999), and
Montreal (2000).
http://www.cs.uu.nl/people/ralf/hw2001.{html,pdf,ps,txt}
Scope
-
The purpose of the Haskell Workshop is to discuss experience with
Haskell, and possible future developments for the language. The scope
of the workshop includes all aspects of the design, semantics, theory,
application, implementation, and teaching of Haskell. Submissions that
discuss limitations of Haskell at present and/or propose new ideas for
future versions of Haskell are particularly encouraged. Adopting an
idea from ICFP 2000, the workshop also solicits two special classes of
submissions, application letters and functional pearls, described
below.
Application Letters
---
An application letter describes experience using Haskell to solve
real-world problems. Such a paper might typically be about six pages,
and may be judged by interest of the application and novel use of
Haskell.
Functional Pearls
-
A functional pearl presents - using Haskell as a vehicle - an idea that
is small, rounded, and glows with its own light. Such a paper might
typically be about six pages, and may be judged by elegance of
development and clarity of expression.
Submission details
--
Deadline for submission:1st June 2001
Notification of acceptance: 1st July 2001
Final submission due: 1st August 2001
Haskell Workshop: 2nd September 2001
Authors should submit papers of at most 12 pages, in postscript format,
formatted for A4 paper, to Ralf Hinze ([EMAIL PROTECTED]) by 1st June
2001. The use of the ENTCS style files is strongly recommended.
Application letters and functional pearls should be labeled as such on
the first page. They may be any length up to twelve pages, though
shorter submissions are welcome. The accepted papers will be published
as a University of Utrecht technical report.
Programme committee
---
Manuel Chakravarty University of New South Wales
Jeremy Gibbons University of Oxford
Ralf Hinze (chair) University of Utrecht
Patrik Jansson Chalmers University
Mark Jones Oregon Graduate Institute
Ross Paterson City University, London
Simon Peyton Jones Microsoft Research
Stephanie Weirich Cornell University
___
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
Re: Showing functions
| Section 6.1.6 of the report says that "Functions are an instance of the | Show class but not | Read." How are functions meant to be shown? The standard prelude | 'specification' doesn't say anything about it. That's a typo. Section 6.3.3 says ``All Prelude types, except function types and IO types, are instances of Show and Read'' Before Haskell 98 there was an instance instance Show (a -> b) where showsPrec p f = showString "" Cheers, Ralf
Re: convex hull
| I need a 'convex hull' implementation in Haskell. | Does anyone know where I can find one? Joern Dinkla has implemented several geometric algorithms in Haskell, see http://goethe.ira.uka.de/~dinkla/cglib.html Cheers, Ralf
Re: When is an occurrence an occurrence
| Gentle Haskellers, | | Here's a Haskell98-typo question. | | Consider this program: | | module M where | | reverse xs = Prelude.reverse (tail xs) | | foo ys = M.reverse ys | | This is legal Haskell98. The call to Prelude.reverse and to M.reverse | must both be qualified, because plain 'reverse' would be ambiguous. | But the definition of reverse does not need to be qualified, becuase it's | a definition! | | | Now, would it be legal to add this type signature to the end of M? | | reverse :: [a] -> [a] | | Or should it be | | M.reverse :: [a] -> [a] | | I can see two arguments | | A) The unqualified form should be legal because the type signature | can only refer to the 'reverse' defined in this module | | B) The unqualified form is ambiguous. All occurrences of 'reverse', | other than the definition itself, must be qualified | | The Report itself does not answer the question clearly, | so I propose to resolve the ambiguity. | | Personally I'm inclined to resolve it in favour of (B). In due course we | may want to allow type signatures for imported things in a module, for | example. Does anyone object? Since it's a Haskell 98 issue, I am in favour of (A): reverse :: reverse :: [a] -> [a] reverse xs = Prelude.reverse (tail xs) Alternative (B) looks rather ugly: M.reverse :: reverse :: [a] -> [a] reverse xs = Prelude.reverse (tail xs) Cheers, Ralf
Re: Haskell 98: partition; and take,drop,splitAt
| Partition | | PROPOSAL: use the filter/filter defn of partition Agreed. | Take and drop I strongly vote for (A) because it _is_ sometimes useful. | splitAt | | PROPOSAL: use the take/drop defn of splitAt Agreed. Cheers, Ralf
re: The Haskell mailing list
| I also agree with Simon that simply making this a moderated list is | not the solution. Perhaps splitting is best. How about | | haskell-info | haskell-talk | | where info carries *brief* announcements, requests for information | and responses to such requests, and talk carries anything and | everything else appropriate to a Haskell list. I like that proposal, Ralf
Re: Fast Finite Maps w/ destructive update
| I am trying to implement data compression code (lzw) and have been using a | home grown binary tree implementation which runs too slowly. | | I would prefer to use a fast/destructive finite map implementation... | Can anyone recommend one? What about tries? They are purely functional ;-) and fast. A (real old) Haskell 1.2 implementation can be found at http://www.informatik.uni-bonn.de/~ralf/Library/Trie.html Chris Okasaki's book on Functional Data structures contains further information. See also, http://www.cs.columbia.edu/~cdo/papers.html#ml98maps HTH, Ralf
Re: Stream of random comments continues
| The discussion of random numbers in Haskell should perhaps | move elsewhere as it is quite restricted, but it shows one | problem with the functional approach to *practical* programming: | in *my opinion* our fascination by the Monadic Approach to | Universe and Everything, and the possibility to program in an | imperative way has a negative side effect. My friends physicists | asked me once after being told that imperative constructs are | possible in Haskell: "so, what's the point in using this language? | Fortran code is simpler than "do" in Haskell..." Huuuh. Did you tell your friend that imperative constructs are the `only' thing possible? Surely not. So I don't quite understand this statement (on a scientific basis). | I would change the | Lennart example by using splitAt instead of take, and continuing the | next | instance with the remaining part of the master sequence. But now you are basically programming within a state monad, the infinite sequence of pseudo-random ints being the state. At its simplest: let (is1, ms1) = splitAt m ms (is2, ms2) = splitAt n ms1 vs do is <- ints m ds <- doubles m However, having re-thought the whole thing I guess it's a good idea to use an infinite stream as the state instead of the seed. As you remarked in a previous mail this would make it simple to provide a different generator. Nonetheless, I still believe that using a monad (note necessarily IO) is the RIGHT approach, because the state is passed implictly and it allows to hide the technical details (how many Ints do you need for an Integer in the range (l,r)?) from the user. Cheers, Ralf
Re: Random comments
| First: I had forgotten that what the Random module actually | gives you is [Integer], not [Int], but the same reasoning | applies. What's the range for the Integers? I guess Int is better suited. | Well, you naturally need functions that convert a list of | [Integer] to what you need. I'm not at all against such functions, | and I think they should be included, e.g. | toDouble :: [Integer] -> [Double] | toInt :: [Integer] -> [Int] | etc. So I might write | let mis = take n (random ss1) | is = take n (toInt (random ss2)) | ds = take n (toDouble (random ss3)) | in ... | where ss1, ss2, ss3 are the seeds. You can get them from an initial | call to randomIO or use some known values if you need to repeat the sequence. My problem with your solution is that you must supply a seed for every call (perhaps you don't know how many do you require) and that you may end up with pseudo-random numbers which are not random at all. Because you choose the seeds badly. That's why I thread the (current) seed through all those value generators. Of course, instead of threadening a seed one could thread an infinite list of Ints. | I think using monads, and specially a powerful one like IO, everywhere is | a mistake. I can't see the need for most uses of random numbers. I agree that the IO monad is not necessary. However, a monad for random values seems perfectly reasonable. Ralf
Re: Random comments
| > The stream-based approach has its problems if one requires random | > values of different types. If this is vital one automatically starts to | > use functions of type Seed -> (value, Seed). | I don't understand at all. Why would random values of different types | require that signature? Why can you use an infinite list of these | other values? Why can't you take the [Int] list of random numbers | and transform it into whatever you want? That's what I do. I guess you would end up with nearly the same code (unless I overlook an obvious alternative in which case I would love to see the simple and straightforward solution ;-). Let's be concrete: say you need n Integers within range (l, r), m Ints and p Doubles. Using a monad-based approach one writes ... mis <- accumulate [ randomInteger (l, r) | i <- [1 .. n] ] is <- accumulate [ randomInt | i <- [1 .. m] ] ds <- accumulate [ randomDouble | i <- [1 .. p] ] return (mis, is, ds) What's your solution based on an [Int] list of random numbers? Ralf
Re: Random comments
| Could somebody - perhaps outside this list - provide a serious | example showing the *necessity* for RandomIO() - the Monadic, | "side-effect" version? In a pure functional language? Well, I'm not outside this list ;-). Honestly, there is no necessity for using the IO monad, it is just a matter of convenience, see below. | I use random numbers from time to time. | I have always used sequences, lazily generated. No problem | with the seed injection/restoring, and - what is *much* more | important: | | No problem with having *several* generators within the program. The stream-based approach has its problems if one requires random values of different types. If this is vital one automatically starts to use functions of type Seed -> (value, Seed). Sooner or later you recognize that you are programming in a state monad. Now, one could define a specialized monad or misuse (if you like) IO. | In a serious application this is useful for generating random | vectors, or for using one generator to decorrelate another. | I agree with the comments of David Tweed. Please give the | People the Power to plug-in several generators, instead of | eine Sprache, eine Kirche, ein ZufallsZahlGeneratorIO()... I don't see why this should be a problem. The dilegent user is always free to plug in new generators, simply by supplying modules which have the same signature as `Random'. | You might answer that a primitive is more efficient. But in | typical simulations or other applications which use random | numbers (Monte-Carlo, etc.) this is usually not as important. It's probably both more efficient and more convenient ;-). Cheers, Ralf
Addendum: randomIO
I wrote ... > The following signature seems quite reasonable to me. > > type Seed = Int > getSeed :: IO Seed > setSeed :: Seed -> IO () > randomInt :: IO Int > randomInteger :: IO Integer > randomDouble :: IO Double I'm getting old ;-). Of course, `randomInteger' requires an additional parameter specifying the range of the random numbers. randomInteger :: (Integer, Integer) -> IO Integer Ralf
Re: Haskell 98: randomIO
| I agree. In fact, I would be most happy with a function getRandom :: IO | Double that returns a random number between 0 and 1. Good point. When trying to develop a testbed for the library of sorting routines I found the library Random completely unusable. There are essentially two reasons: a) I required both random `Int's, `Integer's and `Double's. b) If a test input reveals an error in the code, one should be able to reproduce the run which in turn requires that the initial seed is available. The following signature seems quite reasonable to me. type Seed = Int getSeed :: IO Seed setSeed :: Seed -> IO () randomInt :: IO Int randomInteger :: IO Integer randomDouble:: IO Double `getSeed' obtains a seed in some system-dependent manner. `setSeed' sets the seed for the `randomType' functions. The latter functions all use the same internal seed to be able to produce good random data. [One could perhaps invent a new class to standardize the last three functions but I don't know whether this is worth the effort]. Additionally, one could supply functions which take and return the seed explicitly. randInt :: Seed -> (Int, Seed) randInteger :: Seed -> (Integer, Seed) randDouble :: Seed -> (Double, Seed) Cheers, Ralf
Re: Why I hate n+k
Simon writes ... | Just to amuse you all, here's a quick Haskell 98 quiz: | | What do the following definitions do: | | 1 x + 1 = f x | | 2 (x + 1) = f 2 | | 3 (x + 1) * 2 = f x | | 4 (x + 1) 2 = g x | | | That's right! | | (1) partially defines (+). One could add more equations, thus: | x + 1 = f x | x + other = g x | | (2) is a pattern binding that binds x. It's quite like | | Just x = f 2 | | except that the pattern is an n+k pattern | | (3) is a function binding rather like (1), except that it defines (*). | The (*) operator has two operands: an n+k pattern (x+1) and 2. | | (4) is a new possibility in Haskell 98. | It defines (+), albeit differently to (1). Here the (+) has | three operands, namely x, 1, and 2, so it will have a different | type to the usual (+) but never mind. | | | I don't propose to change this, because in practice it doesn't seem | to cause much of a problem, but it seems pretty confusing. To my mind | the culprit is clear: n+k patterns. But they are staying in Haskell 98. Aaah, n+k patterns again. I am not ashamed to admit that I love n+k patterns and that these examples do not really change my point of view. The major source of confusion is that n+k patterns are admissible in pattern bindings which makes it hard to distinguish them from function bindings defining `+' [(1) vs (2), (3) and (4) are unambiguous]. Personally, I never use n+k pattern bindings but I do use n+k patterns in functions bindings. Don't throw the baby out with the water! If we strive for an unambiguos language which is BTW an ambitious design goal let us nuke n+k pattern bindings but retain n+k patterns in function bindings. On the negative side this adds an irregularity to the language of patterns but one which I would be willing to accept (in view of the advantages of n+k patterns). Cheers, Ralf
Re: Reduction count as efficiency measure?
| Is this true in practice? That is, are there programs which have | different asymptotic running times when compiled under ghc or hbc than | when running under Hugs? | | It would actually surprise me if there were; I'm having a hard time | imagining a realistic optimization that would do this. (Which could | easily be a failure of my imagination.) What about common subexpression elimination? AFAIK neither Hugs nor GHC nor HBC implement CSE, but if they did the asymptotic running time could sometimes radically change. Here is a nice example several first-year students came up with when I asked them to program `maximum'. > maximum [a] = a > maximum (a : as) = if a < maximum as then maximum as else a Thus implemented `maximum' has an exponential running time. Eliminating the double call `maximum as' yields a linear implementation. > maximum [a] = a > maximum (a : as) = let m = maximum as in if a < m then m else a Does this example convince you? Cheers, Ralf
RE: MonadZero (concluded)
| Does this mean that code which relies on ++ and do notation with Maybe | will stop working? ++ is specialized to lists, I'm afraid. Ralf
Re: MonadZero (concluded)
| class Monad m => MonadPlus m where | mzero :: m a | mplus :: m a -> m a -> m a | | Why is this here? It doesn't need to be in the prelude. Just | leave it for the user to define (and then the user may pick | better names, like Ringad, zero, and <+>). -- P Yes, nuke MonadPlus. For Haskell 2 we can put these things in a wonderful Monad library. Ralf
Re: Default Default
| John Peterson writes | | Int is really not a nice | datatype and we shouldn't be allowing it to crop up unexpectedly. | | Yes, but if we believed that, we should use Integer, not Int, for | length. | | You are right, beginners may stub their toe on factorial. On the other | hand, with the default set to Integer, beginners may stub their toe | on bad performance. Anyone familiar with, say, C, will be unsurprised | by the need to switch Int to Integer to get factorial to work, but will | be very surprised by the need to switch Integer to Int to get decent | performance. -- P I'd like to support John P. and Colin R. on this point. The very Haskell beginner enters the Hugs interpreter and types (motivated by his instructor) Prelude> product [1..100] 0 Ops, the instructor forgot that the default default is Int. Beginners who already worry about performance (by a constant factor) should have no problem in adding a default declaration. Having Integer as the default default has also the beneficial side-effect to motivate implementors to improve upon the status quo ;-). Cheers, Ralf
Re: mfail -> fail
| Here's an even better idea: replace mfail with fail. | It is, after all, the fail of the IO monad! | | Option 4'': Monad ((>>=), return, fail) Unfortunately not, fail of IO fame has type IOError -> IO a and not String -> m a as Monad's new member. Here's my suggestion: o Monad ((>>=), return, fail) o throw (thanks Frank) instead of fail for the IO operation o raise for Haskell-2's exception mechanism (raise and handle)? Cheers, Ralf
Haskell 98 libraries
> Haskell 98 libraries > > * Make each module export all the relevant types and functions that the > Prelude defines, so that a programmer who does not import the Prelude > can get access to all the (say) list types and functions by saying > import List. This involves extra exports from modules List, Monad, IO, > Maybe, Char. That's a jolly good idea! In the light of this change we possibly should also add a library module for Either (a type which is currently a bit neglected). > instance Functor (Either a) where > fmap f (Left a) = Left a > fmap f (Right a) = Right (f a) > instance Monad (Either String) where > Left a >>= k = Left a > Right a >>= k = k a > return= Right > mfail s = Left s Many of the functions contained in the library Maybe make sense for Either as well. Cheers, Ralf
RE: MonadZero
| I agree that this is an error that you would like the system to catch. | I disagree strongly with the suggestion that this is an error that you | should expect the *type system* to catch. | | Suppose that the original version of your nuclear reactor driver also | contained a definition: | |inCaseOfEmergency Open = ... | | When an extra constructor is added to the datatype, you would hope that | your compiler might report a "non-exhaustive pattern match" error here, | alerting the programmer to the fact that modifications to this function | definition might be required. This isn't a type error, it's a question | about values within a type, and about whether you manage to cover all | the possibilities. | | Likewise, your definition of controlReactor might reasonably be | expected to generate a "non-exhaustive pattern match" error when | the second constructor is added. | | You'll be seriously misleading designers of nuclear reactor drivers, | as well as those for more mundane appliances, if you tell them that | Haskell's ability to raise a type error in situations like this will | make the language safer. For one thing, it only applies to do notation, | and not to pattern matches in function definitions. For another, it | wouldn't do anything to help in situations where a datatype with two | constructors is modified to add a third. | | So here is good motivation for adding mechanisms to check for exhaustive | pattern matches, but not for choosing between the alternatives that | are being considered for do notation. I fully and strongly agree with Mark's statement except for one minor point ;-). A compiler should issue a warning (as opposed to an error) in both cases. Cheers, Ralf
Re: MonadZero
| I want to make a different plea: keep the language design consistent!
| Yes, the difference between f, g, h is a wart, but let's have one wart
| repeated, rather than two different warts.
I am not convinced. This argument could be reverted to support
alternative 2. Haskell uses patterns in many different places,
monad expressions among other things. Why should we introduce
concepts (irrefutable, unfailable) only for monad expressions?
Why is
head (a : as) = a
legal, but not
do { ... (a : as) <- e ... }
So, to keep the language design consistent, let's adopt 2. The
expression `head []' fails (which means `error "..."' in the Id monad)
and the computation `(a : as) <- e' fails, as well (which means `mfail'
in an arbitrary monad).
A comment on names: I propose to use `fail' for the class method
and to rename IO's fail to `raise' which IMHO is more consistent
(the Report says: the `fail' function _raises_ an exception ...).
Cheers, Ralf
Re: MonadZero
| > 1.Fix up the current version. | > use MonadZero for do expressions with *irrefutable* patterns | > (instead of *unfailable* patterns as now) | > 2.Nuke MonadZero altogether. | > add mfail :: m a to Monad instead I opt for 2. It's certainly true that the second choice breaks existing code, but this can easily be repaired: simply replace MonadZero by Monad and zero by mfail (given that mfail = error "fail" is added as a default). Right? This change is quite undramatic. And it solves a lot of problems.
Re: topdelcs / decls
| just a thought .. why is it that some declarations | (data, type, newtype, class, instance) are only allowed | at the (module) top level? in some cases i'd like to have | more locality, and less namespace pollution. Let me add: local declaration might also increase the expressibility of Haskell! So it's not merely about name space pollution. Haskell's type class system is currently limited in that it is not possible to create a dictionary that depends on dynamic values. Let me give an example: there are two ways of defining a generic sorting routine. > sort :: (Ord a) => [a] -> [a] > sortBy:: Rel a -> [a] -> [a] > type Rel a= a -> a -> Bool As it stands `sortBy' is more general than `sort': I can define `sort' in terms of `sortBy' but not the other way round. [However, sometimes it is far more convenient to implement `sort' than `sortBy'.] > sort = sortBy (<=) If local instance declarations were admissable I could possibly write ... lots of hand-waving ... > sortBy (rel :: Rel a) = sort where instance Ord a where (<=) = rel Hmm. That may look dauting but could possibly be put to work. JUST A THOUGHT Cheers, Ralf
RE: topdelcs / decls
| Your thought would destroy equational reasoning! For example you | would be able to define different equalties on the same data | structure. So Red==Black could be False in one place and True | in another place. Does that make any sense? Of course, it does. You neglect the fact that definitions have scope. You can already define two functions both called say `eq' such that `eq Red Black' yields False in one place and True in another place. Cheers, Ralf
RE: Haskell 98
| > So '---' is not a valid operator symbol, but '-->' is. A line | > of hyphens of | > any length introduces a comment. | > | > | > ] I do not understand the example: if every lexeme consisting of two | > ] or more hyphens begins a comment, `-->' begins a comment! | | No, '-->' does not consist of two or more hyphens; 'consist of' means | 'contains only', and there's a '>' in the lexeme. Is that clearer? Aah, yes, That's clearer. D'accord. | > Allow a type and a class to have the same name | > | > Rejected. It's an un-forced change, and it allows even more | > obscure programs | > than now. Data constructors and type constructors can share | > the same name, | > but data constructors appear only in expressions, and type | > constructors only | > in types, so there's no confusion. But classes appear in types too. | > | > ] No, no, no! Why on earth should Haskell 98 dictate the | > choice of names? | | Interesting! Several people have spoken up about this one, and I don't | feel very strongly either way, so I'm open to persuasion. Just to | articulate | the alternative, I'm proposing that if types and classes can have the same | name, then in export and import lists one would say | class C | for classes, but simply | T | for types (as now). I don't want to get into whether T is a type | synomym, a data type, or a newtype; if we say 'type T' it might be | misleading. | | How does that sound? Sound's good. Needless to say I vote strongly for this alternative. Cheer, Ralf
Re: Haskell 98
| Comments to me directly ([EMAIL PROTECTED]), or the Haskell mailing | list. Here we are ... (comments are marked with `]') Typing of do expressions [...] 2. Nuke MonadZero altogether. Instead, augment the Monad class with class Monad a where ...as before.. mfail :: m a Now all do expressions are in class Monad. You can interpret mfail as a zero if you like. Two reasons for liking this: o It simplifies the typing of do expressions. o Pretty much every monad will have to be in MonadZero in order to do something sensible with do expressions that include patterns. If that's the case, why not simplify and combine the classes? o No known Haskell monad obeys the laws for a zero: m >> zero = m (e.g. Take m to be bottom.) So calling it a zero is a bit of a misnomer. ] I prefer the second option simply because all `do' expressions are then ] in the basic Monad class. One could even add a default definition for ] `mfail' ] ] class Monad a where ] ...as before.. ]mfail :: m a ]mfail = error "computation failed" ] ] Then no changes to existing instances of Monad are required. ] ] BTW I guess the law should read as ] ] m >> zero = zero . The simple-context restriction The question here is whether f :: Eq (h a) => ... g :: Eq [a] => ... should be legal types. In Haskell 1.4 both are illegal; the constraints in a context must take the form (Class tyvar). There are three possibilities: 1. Status quo. Accept that we don't have principal types, and that occasionally hurts. 2. Allow constraints of the form (Class (tyvar types)). This would make f's type signature legal, but still exclude g's. It still permits eager context reduction (as Haskell currently has). It has principal types. But Haskell 2 is going to go further. 3. Allow arbitrary types in contexts. This would make both f and g's type signature legal. This is where Haskell 2 is going; it is sound and implementable. But it forces lazy context reduction, which is a big change, perhaps all the more so because it is largely hidden. Furthermore, it is a change that hbc and nhc might find it hard to track. ] Don't stick to the status quo!!! Types like `Eq (h a)' just occur too ] often (as a rule of thumb they always show up if you mix classes and ] constructor classes). So if (3) is a problem because of lazy context ] reduction adopt (2), but not (1). Lexical and syntactic matters VarIds can begin with "_". The ICFP meeting didn't like this change. Partly because '_' on its own is not a normal identifier, in a pattern at least: it's a wild card. The change was apparently originally motivated by noting that ___ (three consequtive underscores) would lex as _ _ _, clearly a Bad Thing. We agreed to fix it thus: * make '_' lexically a valid identifier character anywhere * but disallow identifiers starting with '_' Thus '___' would lex as '___' but then be rejected. '_' on its own remains a wild-card pattern, and illegal in expressions. ] `_' is a special case whatever option one chooses. So I can see no real ] advantage in disallowing identifiers starting with '_'. Maximal munch rule for '---' Modified. Yes, use the maximal munch rule, but any lexeme consisting of two or more hyphens begins a comment. So '---' is not a valid operator symbol, but '-->' is. A line of hyphens of any length introduces a comment. ] I do not understand the example: if every lexeme consisting of two ] or more hyphens begins a comment, `-->' begins a comment! Allow a type and a class to have the same name Rejected. It's an un-forced change, and it allows even more obscure programs than now. Data constructors and type constructors can share the same name, but data constructors appear only in expressions, and type constructors only in types, so there's no confusion. But classes appear in types too. ] No, no, no! Why on earth should Haskell 98 dictate the choice of names? ] Nobody is forced to use the same names for types and classes, if she or he ] does not like it. But there may be a situation where this is pretty useful. ] The next step is probably to ban the indiscriminate use of recursion ] because one can use recursion to write very obscure programs. ] Sorry for my passionate words but I do not like the tendency here :-(. Allow import decls anywhere in a file Rejected. Most people wanted them to stay at the top. ] The same comment applies here ;-). Remove concept of "special identifier" The idea was to make hiding and qualified into keywords
Re: Instance contexts.
| > I'd like to support Alex here: it is absolutely necessary to relax | > condition 10 of SPJ's list. | | http://www.dcs.gla.ac.uk/~simonpj/multi-param.html | | > Idioms like the one above (`Ord (s a)' or | > `Show (s a)') arise too often and are completely natural. | | One of the great merits of imposing restrictions is that | you hear about when they are irritating :-). (The reverse does | not hold.) Examples like this are jolly useful. | | Ralf: can you supply other examples? Here is another one. It seems that condition 10 hinders the use of abstraction. Consider the following innocent looking definitions > data Tree a = Empty | Node (Tree a) a (Tree a) > deriving (Show) > data Cons a = Cons a (Tree a) > deriving (Show) and suppose that we want to abstract away `Cons's dependency on `Tree'. > data Cons tree a = Cons a (tree a) > deriving (Show) Now, we have a context of the form instance (Show (tree a), Show a) => Show (Cons tree a) which violates condition 10. And note that this might happen as soon as you use higher-order polymorphism (types of kind * -> *). Cheers, Ralf
Re: Scoped typed variables.
| This sounds great, but it could break old code, of course. This would have a | different type under Ralf's proposal than Haskell 1.4: | (id :: a -> a, id :: a -> a) | However, I think something like it is the only sane way to go. Whatever we do, type | variables should scope consistently. With proposal "A" as is (such that it wouldn't | break old code, and just like in hugs 1.3c), a type variable would scope differently |if | it was in a pattern verses being in an expression. Ralf's proposal fixes that |nicely, | and I don't think the cost in old code here would be very high. By the way note that currently it is not possible to enfore that two subexpressions have the same type (asTypeOf works only for some special cases). So if the intent is that both occurences of `id' have the same type (id :: a -> a, id :: a -> a) does not work. Ralf
Re: Scoped typed variables.
| > > Just as a sanity check, following an augmented proposal "A" where we can also | > > annotate the return type as well, consider these: | > > | > > f :: a -> (a -> a) -> a | > > f x = \g -> (g :: a -> a) x | > > | > > f (x :: a) :: (a -> a) -> a = \g -> (g :: a -> a) x | > > | > > Which of these two is correct, and why? Why not both? | > | > Under "A+B", these would be equivalent. Under "A++" (Mark's original | > "A", only, plus the return types), the second of these is "correct" | > (assuming a restricted interpretation of "a" is what was intended), but | > in the first, the a's in sig and body are bound quite separately, so the | > local type annotation would be too general. | > | | I'm not sure what the parenthetical comment about the interpretation of a means - | take the definition at face value. | | I should have been more explicit - I'm interested not in why the first one would | be incorrect, but how, for example, you would explain that to someone learning | Haskell. It's not at all clear to me that people should expect the a's to be | different - I can't think of a good rationale for it (aside from the "don't break | old code" argument, which, if that's the only argument, doesn't seem strong enough | to me). One could also argue that the culprit is Haskell's interpretation of type variables of which Report (p. 34) says: `[...] the type variables in a Haskell expression are all assumed to be universally quantified [..]'. Here is an even more irritating list of possibilities ... rapply :: a -> (a -> a) -> a rapply a f = f a rapply (a :: a) f = f a rapply a (f :: a -> a) = f a rapply a f :: a = f a rapply a f = (f :: a -> a) a rapply a f = f (a :: a) rapply a f = f a :: a rapply a= \f -> f a rapply (a :: a) = \f -> f a rapply a:: (a -> a) -> a= \f -> f a rapply a= \(f :: a -> a) -> f a rapply a= \f -> f a :: a and so forth ... A solution could be to consider the type variables universally quantified at the _outermost_ possible level (currently it's the innermost). So `f e1 ... en = e' means `forall a1 .. am.f e1 ... en = e' where the `ai's are the type variables occuring free in the definition. If we had explicit syntax for universal quantification (which I consider absolutely necessary) the former interpretation could be recovered using explicit quantifiers: ... (f :: forall a.a -> a) ... Ralf PS: I don't like the scope-mixture of type signatures and definitions.
Re: avoiding repeated use of show
| I would be more inclined to use <<. The reason is typing efficiency. | '&' is awkward to be typing frequently immediately after '"'. I do not type that fast ;-). | You are acutally using (.) below. Is there a way to do that (via | Fran like lifting?)? I'm afraid no. | > > instance Stringable ShowS where | > > toStrings = id | > | > This instance declaration is necessary to make `&' useable. Note that | > this is not (Standard) Haskell but works only with Hugs 1.3c (and | > probably with GHC's next release). | | Why does this instance declaration require 1.3c? Also, are there | substantive differences between Hugs 1.3c and GHC 3.3? Are people | prototyping w/ 1.3c and then planning to build with the next GHC? Haskell requires that the instance head is of the form C a1 ... ak where ai are type variables. However, the code _does_ work with GHC 3.2 if the flag `-fglasgow-exts' is on (sorry for the incomplete information). | > > (&) :: (Stringable a, Stringable b) => a -> b -> |ShowS | > > a & b = toStrings a . toStrings b | > | > Note that `&' yields `ShowS' and not `String'. | > | > > val = "the sum of 2 and 2 is " & (2 + 2 :: Int) & " whenever." | | > Furthermore note that `val' has type `ShowS'. If quadratic time | > behaviour is not a problem (does not occur?) you can safely omit the | > `Stringable ShowS' instance and change `&' to `toString a ++ toString b'. | | I am not understanding this last bit. Can you explain further? Well. If you change (<<) to > (<<) :: (Stringable a, Stringable b) => a -> b -> String > a << b= toString a ++ toString b and make nested calls to (<<) you may experience quadratic time behaviour. The standard example involves printing a tree: > data Bush a = Leaf a | Fork (Bush a) (Bush a) > deriving (Show) > > lay :: (Stringable a) => Bush a -> String > lay (Leaf a) = "(Leaf " << a << ")" > lay (Fork l r)= "(Fork " << lay l << lay r << ")" Simply try lay $ leftist [1 .. 1 :: Int] where leftist is defined as follows. > leftist = foldl1 Fork . map Leaf BTW With the original definition of (<<) it is quite easy to make `Bush' an instance of `Stringable'. > instance (Stringable a) => Stringable (Bush a) where > toStrings (Leaf a)= "(Leaf " << a << ")" > toStrings (Fork l r) = "(Fork " << l << r << ")" Maybe cunning, but I like it ;-). Ralf
Re: avoiding repeated use of show
> I would like to avoid using show all the time for printing strings e.g. > > > val = "the sum of 2 and 2 is "++(show $ 2 + 2)++" whenever." > > I would prefer to type something like: > > > val = "the sum of 2 and 2 is "./(2+2)./" whenever." > > -- i can' find a better haskell compatible operator > > I can't simply "show" the arguments of (./) because showing strings adds > quotation marks which I don't want in this context. > > So I tried creating my own Stringable class: > > class Stringable a where > > toString::a -> String > > > (./) :: (Stringable a,Stringable b)=> a->b->String > > x./y = (toString x)++(toString y) Nice idea. I polished the code somewhat ... === > infixr 0 & What about `&' for catenation? > toString :: (Stringable a) => a -> String > toString a= toStrings a "" > class (Show a) => Stringable a where > toStrings :: a -> ShowS > toStringList :: [a] -> ShowS > > toStrings = shows > toStringList [] = showString "[]" > toStringList (a : as) = showChar '[' . toStrings a . showl as > where showl []= showChar ']' > showl (a : as) = showString ", " . toStrings a . showl as The class `Stringable' uses the `ShowS' mechanism to avoid quadratic time behavior and employs the standard trick to allow overlapping instances (Eric Meijer has written a short note about that topic): [Char] and [a] should be treated differently. > instance Stringable Char where > toStringList s= showString s This instance declaration print strings as they are ... > instance Stringable Int > > instance Stringable Integer > > instance Stringable a => Stringable [a] where > toStrings = toStringList > > instance Stringable ShowS where > toStrings = id This instance declaration is necessary to make `&' useable. Note that this is not (Standard) Haskell but works only with Hugs 1.3c (and probably with GHC's next release). > (&) :: (Stringable a, Stringable b) => a -> b -> ShowS > a & b = toStrings a . toStrings b Note that `&' yields `ShowS' and not `String'. > val = "the sum of 2 and 2 is " & (2 + 2 :: Int) & " whenever." Furthermore note that `val' has type `ShowS'. If quadratic time behaviour is not a problem (does not occur?) you can safely omit the `Stringable ShowS' instance and change `&' to `toString a ++ toString b'. > render:: (Stringable a) => a -> IO () > render a = putStr (toString a) `render' is quite flexible: ? render val the sum of 2 and 2 is 4 whenever. ? render (toString "aaa") aaa ? render "aaa" aaa ? render (toStrings "aaa") aaa === > Is there any way to convince Haskell to just resolve these numbers to > SOMETHING by default? Then I can just declare that type an instance of > Stringable. Unfortunately not. I did not succeed in persuading SPJ ;-). See http://www.cs.chalmers.se/~rjmh/Haskell/Messages/Display.cgi?id=445 HTH, Ralf
Re: Monomorphism
One of the original motivations for questioning the DMR steems from the fact that function definitions expressed as simple pattern bindings are sometimes rejected. The definition sum as = foldr (+) 0 as is accepted but sum = foldr (+) 0 is not which is admittingly irritating. Couldn't the compiler silently eta-expand the second definition into the first thus turning a simple pattern binding into a function binding? Ralf
Re: Instance contexts.
> Ralf: can you supply other examples? Sure thing. A while ago I implemented several popular priority queue structures. Being tired of proving them correct I worked out a simple method of checking their correctness (or rather: the absence of errors) at run-time. The idea is to cross-check a new implementation with a trusted old implementation. > newtype ControlBy q p a = Control (q a, p a) > > instance (PriorityQueue q a, PriorityQueue p a, Show (p a)) > => PriorityQueue (ControlBy q p) a where > empty = Control (empty, empty) > single a = Control (single a, single a) > meld (Control (q1, p1)) (Control (q2, p2)) > = Control (meld q1 q2, meld p1 p2) > splitMin (Control (q, p)) = case (splitMin q, splitMin p) of > (Null, Null) -> Null > (Null, Cons _ _) -> error (show p ++ ": priority queue is not empty") > (Cons _ _, Null) -> error (show p ++ ": priority queue is empty") > (Cons a q', Cons b p') > | a == b -> Cons a (Control (q', p')) > | otherwise -> error (show p ++ ": wrong minimum") To be able to print the faulty queue a context of the form `Show (p a)' is required. [I would guess that this is a common idiom.] I `solved' the problem by introducing a class Dump q which was basically a higher-order copy of Show. > One possible choice would be to insist that the context of > an instance decl constrained only proper sub-expressions of > the type on the RHS. Alex's example would be fine then, but > perhaps others might not? This does not help here. Cheers, Ralf
Re: type synonyms
> data / type / newtype: > > i'd like to have these choices > > type T1 = record C1 .. | C2 .. > type T2 = T1 > type T3 = new T2 > > with T2 identical to T1, > and T3 being an identical copy of T2 (but different from T2) > inheriting all its constructors and operations. That's basically newtype with the data constructor omitted (I would prefer data to record). Unfortunately, this seems to be incompatible with the class system. (There was a long discussion on the Standard Haskell discussion list, unfortunately the entry vanished). Ralf
Re: monad transformers and lift
> Suppose I have the following class of monad transformers: > > class (Monad m, Monad (t m)) => MonadT t m where > lift :: m a -> t m a > > and several instances of the class: > > instance MonadT MT1 where ... > instance MonadT MT2 where ... > . . . > instance MonadT MTn where ... > > I obtain a new monad composing monad transformers through the IO monad: > > type MyMonad = MT1 (MT2 (... (MTn IO))) > > And now, if I want to lift "putStrLn" I must write: > > myPutStrLn = lift . lift . ... lift . putStrLn > > This works but looks ugly. > > The question is: > Is there a way that the system could detect how many > lifts are necessary to select the right function? Yes, there is a way. It's a bit painful but it works. The idea is to overload the IO primitives as well. This is in accordance with the approach that a computational feature (here IO) is encapsulated in a superclass of Monad. > class (Monad io) => IOMonad io where > putChar :: Char -> io () > putStr:: String -> io () > getChar :: io Char > getLine :: io String > getContents :: io String > writeFile :: FilePath -> String -> io () > appendFile:: FilePath -> String -> io () > readFile :: FilePath -> io String > fail :: IOError -> io a > catch :: io a -> (IOError -> io a) -> io a Now, you have to lift the operations through the various monad transformers (typically using lift) and to make IO an instance of IOMonad. > instance IOMonad IO where > putChar = Prelude.putChar > putStr= Prelude.putStr > getChar = Prelude.getChar > getLine = Prelude.getLine > getContents = Prelude.getContents > writeFile = Prelude.writeFile > appendFile= Prelude.appendFile > readFile = Prelude.readFile > fail = Prelude.fail > catch = Prelude.catch HTH Ralf
Re: multi param type classes
> you want to lift this restriction: > > > The type of each class operation > > must mention all of the class type variables. > > how would you resolve ambiguities? > probably by requiring an explicit type signature > at the point of usage. No longer ;-). I find SPJ's summary on http://www.dcs.gla.ac.uk/~simonpj/multi-param.html convincing. The point is that you simply _cannot_ resolve the ambiguity at the point of usage. Furthermore, an alternative is at hand (for the motivating example I gave). Ralf
Re: MPTC: class type variables
> I saw Mark yesterday, and have made quite a few changes > as a result. I've tried to address your points, and those > made by others, but you'll have to judge how successfully! > > http://www.dcs.gla.ac.uk/~simonpj/multi-param.html > > Anyway, you might want to take another look. Sigh. The type of each class operation must still mention all of the class type variables. However, I now see more clearly why this restriction is necessary. The idea to split the class into two is nice and solves the problem. BTW The definition contains a typo: class CollE s where empty :: s class CollE s => Coll s a where insert :: s a -> a -> s a The last line should probably read insert :: s -> a -> s Cheers, Ralf
Re: Structure of monads in an abstract form?
> I think you can "encode", or "mimick" every monad by the following type,
> which is the monad of continuations:
>
> type M a = (a -> Action) -> Action
>
[...]
> Unfortunately the Haskell type system is often too restrictive to encode
> the wanted features. I have for example no idea how to do lists in this
> setting, without doing dirty type hacks in Haskell (but it _is_
> possible... :-).
You need second-order types or local universal quantification. First
note that
> type M a = forall action. (a -> action) -> action
is essentially isomorphic to `a'. A monad capable of backtracking is
obtained via
> type M a = forall action. (a -> action -> action) -> action -> action
We can even turn it into a backtracking monad transformer:
> type T m a = forall action. (a -> m action -> m action) -> m action -> m action
For more information see my FLOPS'98 paper.
Cheers, Ralf
@inproceedings{Hin98Pro,
address = {Singapore, New Jersey, London, Hong Kong},
author= {Hinze, Ralf},
booktitle = {Third Fuji International Symposium on Functional and Logic
Programming (FLOPS98)},
month = apr,
publisher = {World Scientific},
title = {Prological Features in a Functional Setting --- Axioms and
Implementations},
year = 1998
}
Re: type errors
> Ok, I did not reconize this solution, it seems to me the (nearly) proper one. > But why not write: > >class => Dictionary dict where >delete :: (Eq key, Ord key) => key -> dict key dat -> dict key dat >... > > So one could avoid multiparamter classes at all. The two types key and dat > should be inferred by the type of dict (which is expressed by 'dict key dat'). I > can't think about a dictionary where key or dat are not associated with dict. That's the usual approach taken with single parameter type classes. However, not every implementation for finite maps (the functional programmer's term for dictionary) works for all element types. Think of tries or general tries (see Okasaki's book `Purely functional data structures', p. 163-169). Or else we could have a different restriction on the element types, eg (Hashable key) instead of (Ord key) for hash based implementations. That said the following declarations seems appropriate (cf PFDS, p. 204): class FiniteMap map k where empty :: map k a insert :: k -> a -> map k a -> map k a delete :: k -> map k a -> map k a instance (Ord k) => FiniteMap SplayTree k where instance (Hashable k) => FiniteMap HashTable k where Ad-hoc tries: instance FiniteMap Trie [k] where Tries where the mapping from edge labels to tries is parametrised: instance (FiniteMap m k) => FiniteMap (Trie m) [k] where Cheers, Ralf
Re: what is leaking?
> When I try to execute this: > > > result = foldl (+) 0 [1..10] > > main = putStr $show (result `mod` 10) > > Hugs gives: ERROR: Garbage collection fails to reclaim sufficient space > GHC gives: Stack space overflow: current size 262152 bytes. > > Why would this have an error? The list should be constructed lazily as it > is consumed by the sum. I assume I have a space leak but I can't figure > out why. `foldl' constructs the expression ... 3+(2+(1+0)) but does not evaluate it. A common space leak with lazy evalution, see Paulson, ML for the working programmer, p.47. Try this one > strictFoldl :: (Eval b) => (b -> a -> b) -> b -> [a] -> b > strictFoldl (*) = f > where f e [] = e > f e (a:x) = strict f (e * a) x > result= strictFoldl (+) 0 [1..10] > main = putStr $ show (result `mod` 10) Cheers, Ralf
Re: Syntax dubion
> if I write
>
> (a &&& b) x = a x && b x
>
> hugs accepts it, but ghc rejects it. I think that ghc is correct in
> that the report only allows
>
> funlhs
> ->
>var apat {apat }
> |
>pati+1 varop(a,i) pati+1
> |
>lpati varop(l,i) pati+1
> |
>pati+1 varop(r,i) rpati
>
> ie no () and no extra arguments, but given that one may want to define
> higher order functions this way, we ought to make the language allow it.
>
> Can anyone argue against it?
No, I have been bitten by this restriction several times (I even sent
a similar script as a bug to glasgow-bugs). On page 90 of the Haskell
Report we even find
f . g = \ x -> f (g x)
while Miranda TM allows
(f. g) x = f (g x)
Taking Miranda's syntax as a source of inspiration we could
modify funlhs to
funlhs-> var apat {apat}
| pati+1 varop(a,i) pati+1
| lpati varop(l,i) pati+1
| pati+1 varop(r,i) rpati
| pati+1 varop(r,i) rpati
| ( funlhs ) {apat}
Any objections?
Cheers, Ralf
Re: Teaching Haskell
> CUP just released my book on "Purely Functional Data Structures". I just got hold of a copy. My impression: it is *really* worth reading. Ralf
Re: laws for MonadPlus?
> what laws should hold for the (++) operation? Associativity and leftward distributivity are missing in the Report: (m ++ n) ++ o = m ++ (n ++ o) (m ++ n) >>= k = (m >>= k) | (n >>= k) On the other hand right distributivity does not hold in general. Conversely, the report also requires zero to be a right zero of >> which I do not support (if you combine backtracking and exception handling you probably expect raise e >> zero = raise e ). HTH, Ralf
Re: FW: Exceptions are too return values!
> I'd be interested to know what people think of this. > Here's a reasonable design for exceptions in Haskell: > ... > The neat thing about this is that the exceptions can > be *raised* in arbitrary purely functional code, without > violating referential transparency. The question of > which exception is chosen is done in the IO monad, where > of course it is allowed to be non-deterministic. > The implementation does not keep sets of exceptional values, > of course. It simply propagates the first one it trips > over to the nearest enclosing handler. That's neat indeed. What is especially nice is the ability to catch `error' exceptions. > We're implementing an experimental version of this > in GHC, integrated with the IO monad exceptions, so that > > handle :: (IOError -> IO a) -> IO a -> IO a > > and we add an extra constructor (UserError String) to the > IOError type for exceptions raised by raise). The fact that the type of exceptions is fixed (`String' or `IOError') is a weak point of the design (compared to Standard ML). It forces the programmer to encode exceptions as strings which is not what I would call elegant. [I weakly recall that there was a discussion on this point some years ago.] However, I see no way to improve the design :-( other than extending Haskell (with extensible sum types a la SML's `exception' declaration). > One merit of the system is that it chops out a tremendous > number of run-time error checks in the IO monad, since > we are now free to implement the mechanism with standard > stack-unwinding techniques. Result: much better I/O performance. I love performance gains ;-). Cheer, Ralf
Re: How to do Exceptions in Haskell (I think)
> would it be a solution if you defined > > > data RetVal b a = Result a | Exception b > > in this case you could say > > > instance Monad (RetVal b) where > > return = Result > > Result x >>= f = f x > > Exception x >>= f = Exception x Incidentally, the predefined data type `Either' may be used for this purpose. > instance Monad (Either a) where > Left a >>= k = Left a > Right a >>= k = k a > return= Right > > raise :: a -> Either a b > raise s = Left s `Right' means ok ;-). Cheers, Ralf PS: Hallo Peter.
Inference of instance declarations
[This is a repost of an email I sent yesterday to `[EMAIL PROTECTED]'. For some reasons it did not come through. Either the moderator didn't like it or something is wrong with `haskell.org'. I tacitly assume the latter ;-). RH] [This email is mainly directed to the type and class system experts among us.] To come right to the point I wonder whether it is technically possible to derive instance declarations? Consider the following declarations. > class Flatten tree where > flatten :: tree a -> [a] > > newtype Id a = Id a > > flatten (Id a)= [a] As it stands this is not legal Haskell (Hugs complains `Repeated definition for variable "flatten"'). If we rename `flatten' to `flattenId', Hugs is perfectly happy and infers the type `flattenId :: Id a -> [a]'. So why not automatically infer the following instance declaration (on the grounds that we know that `flatten' is overloaded and assuming that the name clash is not just accidental)? > instance Flatten Id where ... Given the following group of declarations > data Fork tree a = Fork (tree a) (tree a) > > flatten (Fork l r)= flatten l ++ flatten r we would infer the instance declaration > instance (Flatten tree) => Flatten (Fork tree) where ... Note that if we rename the occurence of `flatten' on the lhs Hugs infers the type `(Flatten tree) => Fork tree a -> [a]'. Things become interesting if we consider recursive types. > data Bush a = Leaf a | Fork (Bush a) (Bush a) > > flatten (Leaf a) = [a] > flatten (Fork l r)= flatten l ++ flatten r Even if we rename `flatten' on the lhs the program does not typecheck (hugs complains `Bush is not an instance of class "Flatten"'). If we rename the occurences of `flatten' on the rhs as well hugs infers the type `Bush a -> [a]' giving rise to the following instance declaration. > instance Flatten Bush where ... So here is my question: is it always possible to automate this process (even in the presence of mutual recursive type definitions and multiple parameter type classes)? As an aside, note that it is not always possible to turn a function binding into an instance declaration because Haskell has no type abstractions. Consider the function binding, > flatten ts= concat [ flatten t | t <- ts ] which has type `(Flatten t) => [t a] -> [a]'. Unfortunately, `[t a] = [] (t a)' does not match `tree a'. The type composition of `[]' and `t' is not expressible without introducing an auxiliary type (like `newtype Compose t u a = Compose (t (u a))'). Finally note that I do not ask whether it is desirable to omit instance declarations. I do not think that it is always desirable. However, there are situations where one would wish that instance declarations were less heavyweight. For example, if the class comprises only a single method or if it is used only locally within a module. Or during program development: I often use hug's `:type' command to document my program; wouldn't it be nice if one could use a similar mechanism to infer instance declarations (especially if the types are very complicated). Cheers, Ralf
Re: quicksort and compiler optimization
> Ok, clearly I was wrong about list concatenation, but I think I have now > figured out what was bothering me about Ralf's objection to the of ++. > > The argument that the use of ++ in qsort means too many traversals of the > list makes sense if ++ is strict (or you are using a non-lazy language), > but I don't see why the list concatenation needs to happen until you are > going to traverse the list anyway. Laziness means, as far as I understand > it, that for example: > > > testlaziness =take 5 (map (2+) [1,2..]++[5,6..]) > Doesn't fail (it doesn't). > > In other words, you only traverse the list when it is > necessary. So, the time it takes to traverse is time you were going to > spend anyway and therefore ++ is effectively a constant time operation > (without destructive updates!). > > -Alex- > > PS. I want to thank everybody for all the response to this, it has been > very educational. Here is another educational one ;-). You are, of course, right that my estimation about (++) running's time is sometimes a crude approximation as Haskell is non-strict. However, one has to be very careful in drawing conclusions such as `++ is effectively a constant time operation'. Here is the whole story: In a strict language life is easy ;-), the arguments to a function are already evaluated so (++) takes time linear in the length of its first argument. [] ++ bs= bs (a : as) ++ bs = a : (as ++ bs) In Haskell (++) forces it's first argument as to decide which equation should be applied. Hence the running time is _not_ constant. Consider slowsort again, > qsort :: (Ord a) => [a] -> [a] > qsort [] = [] > qsort (a : as)= qsort [ b | b <- as, b <= a ] > ++ a : qsort [ b | b <- as, b > a ] If the pivot element `a' is always the maximal element of the list (as in `qsort [100, 99 .. 1]') `qsort' yields (essentially) an expression of the form (...(([] ++ [a1]) ++ [a2]) ++ ... ) ++ [an] To access the first element of this `list' n unevaluated calls to (++) must be reduced: the outermost call to (++) triggers the evaluation of it's first argument which in turn ... Evaluating the complete list then takes O(n^2) steps. Of course, the incremental nature of (++) is sometimes used to good effect. Take, for example, the queue and deque implementations of Okasaki. Cheers, Ralf
Re: quicksort and compiler optimization
> > > o it uses (++) to catenate the results of the recursive calls (note that
> > > (++) takes time proportional to the length of its first argument).
>
> This also seems wierd. Concatenation is a frequent enough operation on
> lists. Give such frequency, shouldn't the internal representation of a
> list include a pointer to its last element just to ensure that
> concatenation is constant time? I realize that you can't point to the end
> of a lazy list, but concatenation is not relevant to lazy lists.
Haskell is a lazy language; a list is usually an expression which
gradually evaluates to a list if forced. Hence your solution is not as
easy to implement as it seems (consider the list [1 ..]). There is
another point: your solution strongly suggests that a destructive
update is used to catenate the two lists which would violate the
principle of referential transparency (consider the expression as ++
as).
If catenation is used frequently one should use a suitable data type
which supports constant catenation. Chris Okasaki's tutorial on
functional data types
http://foxnet.cs.cmu.edu/afs/cs.cmu.edu/project/fox/mosaic/people/cokasaki/papers.html#ssafp96
contains a collection of sequence data types (the paper is _really_ worth
reading).
> You recursively partition the list based on the first character not
> already processed. So if you have a list like:
>
> [alex,fergus,robert,allen,frank,ralf]
>
> At the next stage you have:
> [(a,[alex,allen]),(f,[fergus,frank]),(r,[robert,ralf])]
>
> It takes at most m passes until each node has only one leaf
> [(a,[(al,[(ale,[alex]),(all,[allen])])]),(f,[(fe,[fergus]),(fr,[frank])]),
> (r,[(ra,[ralf]),(ro,[robert])])]
>
> There are many details to getting this right, but this is the general
> idea.
>
> As I write this, I realize I have no idea how to think about this in
> Haskell. Does the Haskell type system support this? How do I describe
> this tree data structure and maintain a list of leaves accross the
> datastructure?
The data structure you request is a trie or a suffix tree (the Boolean
flag indicates whether the empty list is contained or not).
> data Trie a = Leaf [a] -- leaf node
> | Node [(a, Trie a)] Bool -- inner node
The sorting algorithm is relatively easy to formulate if the elements
to be sorted are lists themselves (recall that a string is a list of
characters). To construct a level in the tree one could use bucket sort.
[The empty list must be considered separately.]
> import Array
>
> bucketSort bs x = [ b | b@(_, y) <- assocs bins, not (null y) ]
> where bins= accumList bs [ (a, as) | (a : as) <- x ]
>
> accumList :: (Ix a) => (a, a) -> [(a, b)] -> Array a [b]
> accumList = accumArray (flip (:)) []
> example = ["alex", "fergus", "robert", "allen", "frank"
>,"ralf"]
The expression
bucketSort ('a','z') example
yields
[('a', ["llen", "lex"]), ('f', ["rank", "ergus"]), ('r', ["alf", "obert"])]
The drawback is that the size of the `alphabet' contributes to the
running time. A few pointers are probably helpful: Robert Giegerich and
Stefan Kurtz have done some work on suffix tree constructions, see
http://www.techfak.uni-bielefeld.de/techfak/persons/kurtz/publications.html
HTH, Ralf
Re: quicksort and compiler optimization
> Also it misses a few useful optimizations, such as median-of-three
> partitioning. For descriptions of that and other ways to speed
> up quicksort, see Sedgewicks "Algorithms in C" or "Algorithms in Pascal"
> (I'm afraid Sedgewick didn't write an "Algorithms in Haskell" ;-).
Median of three more or less assumes that indexing can be done in
constant time which is not the case for the list base variants of
quicksort. Here is another pointer ...
article{BMc93Eng,
author= "Bentley, Jon Louis;McIlroy, M. Douglas ",
title = "Engineering a Sort Function",
year = 1993,
journal = "Software --- Practice \& Experience",
volume= 23,
number= 11,
pages = "1249--1265",
month = nov
}
The SML library contains an SML version of that code (as far as I
remember).
Ralf
Re: quicksort and compiler optimization
> The tutorial defines: > > quicksort []= [] > quicksort (x:xs) = quicksort [y | y <- xs, yy>=x] > > This code strikes me as twice as slow as it could be because it seems to > requires two loops through the list on each recursive call. I guess it is only included in the tutorial in order to demonstrate the use of list comprehensions. You are right, the definition has several drawbacks (besides the fact that quicksort (aka slowsort) is _really_ a bad sorting algorithm). o it traverses the list twice, o it has a space leak (xs is alive until the second traversal is done), o it uses (++) to catenate the results of the recursive calls (note that (++) takes time proportional to the length of its first argument). The standard library offers `partition'. > qsort2:: (Ord a) => [a] -> [a] > qsort2 [] = [] > qsort2 (a : as) = qsort2 l ++ a : qsort2 r > where (l, r) = partition (>= a) as qsort2 still uses (++); use accumulating arguments to eliminate them (see Paulson, ML for the working programmer). > qsort4:: (Ord a) => [a] -> [a] -> [a] > qsort4 [] x = x > qsort4 [a] x = a : x > qsort4 (a : as) x = partition [] [] as > where > partition l r [] = qsort4 l (a : qsort4 r x) > partition l r (b : bs) > | b <= a = partition (b : l) r bs > | otherwise = partition l (b : r) bs The grand final: Lennart Augustsson's variant. Note that `qsort4' ist not stable. By duplicating the code we obtain a stable variant (it additionally takes an ordering predicate as an argument). > qsort :: (a -> a -> Bool) -> [a] -> [a] -> [a] > qsort (<=) []y= y > qsort (<=) [a] y= a:y > qsort (<=) (a:x) y= qpart (<=) a x [] [] y @qpart@ partitions and sorts the sublists. Note that @l@ and @r@ are in reverse order and must be sorted with an anti-stable sorting. > qpart (<=) a [] l r y = rqsort (<=) l (a : rqsort (<=) r y) > qpart (<=) a (b:x) l r y > | a <= b = qpart (<=) a x l (b:r) y > | otherwise = qpart (<=) a x (b:l) r y @rqsort@ is as @qsort@ but anti-stable, ie reverses equal elements. > rqsort:: (a -> a -> Bool) -> [a] -> [a] -> [a] > rqsort (<=) []y = y > rqsort (<=) [a] y = a:y > rqsort (<=) (a:x) y = rqpart (<=) a x [] [] y > rqpart (<=) a [] l r y= qsort (<=) l (a : qsort (<=) r y) > rqpart (<=) a (b:x) l r y > | b <= a = rqpart (<=) a x (b:l) r y > | otherwise = rqpart (<=) a x l (b:r) y Hope this helps. Ralf PS: If you are interested in sorting algorithms take a look at http://www.cs.uni-bonn.de/~ralf/PQSort.ps.gz The paper is a latexed email that contains a collection of (good) sorting algorithms ;-).
Re: Threading Monads
Graeme Moss writes > A question born out only of curiosity: > > Can anyone provide a definition of `thread' equivalent to this: > > > thread :: Monad m => [a -> m a] -> a -> m a > > thread [] a = return a > > thread (k:ks) a = k a >>= thread ks > > not using pattern matching (eg. using map or fold) that does not have > a space leak? You can swap the arguments round if necessary. Here's > an example of what it does: > > thread [c1,c2] a > = c1 a >>= thread [c2] > = c1 a >>= (\b -> c2 b >>= thread []) > = c1 a >>= (\b -> c2 b >>= (\c -> return c)) > > The following: > > > thread :: Monad m => [a -> m a] -> a -> m a > > thread ks a = foldl (>>=) (return a) ks > > is equivalent but evaluates the entire list before starting to execute > an application of (>>=): > > foldl (>>=) (return a) [c1,c2] > = foldl (>>=) (return a >>= c1) [c2] > = foldl (>>=) ((return a >>= c1) >>= c2) [] > = (return a >>= c1) >>= c2 > > and the following: > > > thread :: Monad m => [a -> m a] -> a -> m a > > thread ks a = foldr (flip (>>=)) (return a) ks > > reverses the order of the applications _and_ space leaks: > > foldr (flip (>>=)) (return a) [c1,c2] > = (flip (>>=)) c1 (foldr (flip (>>=)) (return a) [c2]) > = (foldr (flip (>>=)) (return a) [c2]) >>= c1 > = ((flip (>>=)) c2 (foldr (flip (>>=)) (return a) [])) >>= c1 > = ((foldr (flip (>>=)) (return a) []) >>= c2) >>= c1 > = (return a >>= c2) >>= c1 > > You can use any of the Prelude or Monad library functions. > > Graeme. > > PS. I don't know the answer, but no, this is not a homework > exercise. :-) Hmm. Seems not too difficult. But probably I am missing something. > thread:: (Monad m) => [a -> m a] -> a -> m a > thread [] a = return a > thread (k:ks) a = k a >>= thread ks First Step. Rewrite the above definition so that the structural recursion becomes apparent. > thread [] = \a -> return a > thread (k:ks) = \a -> k a >>= thread ks Second Step. Replace the explicit recursion. > thread= foldr (\k sol -> \a -> k a >>= sol) return Third Step. Tidying things up. > thread= foldr (\k sol a -> k a >>= sol) return I tested the definition using > inc n = print n >> return (n + 1) and do thread (replicate 10 inc) 0; putStrLn "done" Seems to work fine. Does this qualify as a solution? Cheers, Ralf
Re: haskell and exceptions
Matthias Fischmann writes ... > I am now trying to learn Haskell for half a week and I like it a lot. > But I still did not find out too much about exception handling. Is it > possible that there is no ml-like mechanism with `raise' and `handle' > built in? Yes, I know about types like > > data Result t = ERROR | Yes t > > and I also read the chapter in the report about IO, monads, and > userError. But this seems all a little clumsy compared to the elegant > and simple exceptions in standard ml or even ugly languages like java. > > Did I miss the point? Are there exceptions libraries? Is there any > extension to Haskell in some existent implementation that handles my > needs? How do you handle exceptions in your Haskell programs? No, there are no extensions for handling exceptions. Some may think that this is a bug but I think it's a feature ;-). First of all it's against Haskell's spirit of being a pure functional language. Consider raise First + raise Second handle First => 1 | Second => 2, what is the value of this expression? It clearly depends on the order of evaluation. SML defines this rigorously (right?). However, Haskell is a lazy language, so even if the language designers would undergo the task of defining the evaluation order, this is nothing which is easy for the user to understand. I usually try to avoid partial functions. That's easier as one might suppose at first (if one is willing to invent new data types). Consider operations on priority queues. > data OptPair a b = Null > | Pair a b > > class PriorityQueue q where > empty :: (Ord a) => q a > meld :: (Ord a) => q a -> q a -> q a > splitMin :: (Ord a) => q a -> OptPair a (q a) Instead of defining `getMin' and `deleteMin' which are both partial functions we define `splitMin' which combines both. Here is a simple application of `splitMin'. > toOrderedList q = case splitMin q of > Null -> [] > Pair a q -> a : toOrderedList q For error reporting and alike I usually use an exception monad. Hope this helps, Ralf
RE: insert sort with foldr
> Yes, you are right, but that is the same function that I wrote in my > original message as 'newfoldr': > > newFoldr::(a->[a]->b->b)->b->[a]->b > newFoldr f c [] = c > newFoldr f c (x:xs) = f x xs (newFoldr f c xs) Well, I merely wanted to throw in the technical term. > I asked if that function (structural recursion over lists) was a > 'fundamental' combinator. I know that there is not a clear definition of > fundamental combinator. IMHO, there should be a set of recursive > combinators in the standard prelude or in Haskell libraries that allowed > programmers to avoid recursive definitions in their programs. Each of those > combinators could be considered 'fundamental'. [Just for fun: try to define `merge' with `newFoldr' (it's possible, but it will take some time to figure out the definition). Do you find the result readable, or would you prefer the recursive definition?] If you ask for fundamental combinators, here is one I find quite useful. > foldm :: (a -> a -> a) -> a -> [a] -> a > foldm (*) e []= e > foldm (*) e x = fst (rec (length x) x) > where rec 1 (a:x) = (a, x) > rec n x = (a * b, z) > where m = n `div` 2 > (a, y)= rec (n - m) x > (b, z)= rec m y > > mergeSort = foldm merge [] . map (\a -> [a]) Regards, Ralf
Re: insert sort with foldr
Dear Jose, > I am trying to define common functions with recursive combinators > avoiding recursive definitions. I have found some problems with > the "insert" function that inserts an element x in an ordered list xs > This function is used when you define insertion sort as "foldr insert []" > > -- First attempt > insert::(Ord a)=>a->[a]->[a] > insert x = foldr (\x (y:ys) -> if x < y then x:y:ys > else y:x:ys) [x] That looks like bubbling an element down (ie `foldr insert []' yields bubble sort rather than insertion sort). BTW I like to think of `foldr' as a special case of _structural recursion on lists_. > structuralRecursionOnLists > :: solution -- base > -> (a -> [a] -> solution -> solution) -- extend > -> [a] -> solution > structuralRecursionOnLists base extend > = rec > where rec [] = base > rec (a : x) = extend a x (rec x) > > insertionSort :: (Ord a) => [a] -> [a] > insertionSort = structuralRecursionOnLists > [] > (\a _ s -> insert a s) > > insert:: (Ord a) => a -> [a] -> [a] > insert a = structuralRecursionOnLists > [a] > (\b x s -> if a <= b then a : b : x else b : s) Regard, Ralf
Re: Sets as monads?
> 1) Is it possible for a set to define a monad? Monads require true polymorphism. Hence the answer is no (from Haskell's perspective) if there are constrains on the element type (like Eq oder Ord). > 2) Does anyone know if it's possible to define an instance of monads >for sets in Haskell? Even with multi-parameter type classes and >even if the definition of the Monad class is adapted, this seems >impossible to me. Let's assume that we may fiddle around with the class definition. Here is another possibility which is missing on your list (no mp type classes, just plain Haskell 1.4 ;-). > module Set( module Set ) > where > > import Prelude hiding ( Monad(..) ) > class Monad m where > return:: (Eq a) => a -> m a > (>>=) :: (Eq a, Eq b) => m a -> (a -> m b) -> m b We simply add the constrains to the method contexts. BIG disadvantage: one has to adapt the class definition if the constrains change. BIG advantage: no fiddling around with multiple parameters (which may be a pain). > instance Monad Set where > return= setSingleton > m >>= k = setUnion (setMap k m) > newtype Set a = Set [a] > instance Eq a => Eq (Set a) where > Set s == Set t= undefined > setUnion :: (Eq a) => Set (Set a) -> Set a > setMap:: (Eq a, Eq b) => (a -> b) -> Set a -> Set b > setSingleton :: a -> Set a > setUnion = undefined > setMap= undefined > setSingleton = undefined Cheers, Ralf
Re: Sorting and Type Classes
[Benchmark suckers and implementors only] Chris writes ... > While experimenting with the sorting algorithms that have been posted here > recently I discovered that the benchmarks were being quite seriously distorted > by the use of type classes to implement some of them. Even the use of `Ord a' > contexts instead of passing the compare method explicitly was introducing some > minor distortions. Here are the results with type classes eliminated, except > for `pairingSort0', the original `pairingSort' as implemented with the > `PriorityQueue' type class, and "nmsort'", a variant of `nmsort' using `Ord a' > contexts. Yes, you are right. I made the same observation. Here are my results ... [fastSort is actually pairingSort without classes, the other functions are as in my previous posting.] +---+ |ghc| And the winner is ... [you should probably enlarge your window] +---+ 100.000 | < |<= | > |>= |== | 1 2* | 1..100* | 2 1* | 100..1* | 1 2 2 1* |random merge | 3.60 | 3.79 | 2.72 | 3.42 | 2.88 | 6.49 | 12.96 | 6.53 | 12.41 | 6.42 |-- bottom-up | 2.17 | 2.36 | 2.03 | 2.09 | 2.18 | 6.49 | 12.92 | 6.47 | 12.55 | 6.43 |-- heap |-- |-- |-- |-- | 22.12 |-- | -- |-- |-- |-- |-- pairing | 1.50 | 1.64 | 2.24 | 2.37 | 1.47 | 2.46 | 4.01 | 2.43 | 4.40 | 2.36 | 10.65 Jon's | 1.07 | 1.31 | 1.12 | 1.20 | 2.21 | 2.93 | 3.43 | 2.88 | 3.48 | 2.81 | 8.24 braun | 26.14 | 22.31 | 21.95 | 21.64 | 7.72 | 14.73 | 20.97 | 14.69 | 20.96 | 14.54 | 23.24 smooth | 0.25 | 0.41 | 0.26 | 2.98 | 0.29 | 4.24 | 3.27 | 4.29 | 3.24 | 4.26 |-- splay | 0.77 | 0.84 | 0.79 | 1.84 | 0.72 | 2.34 | 8.92 | 3.16 | 6.11 | 2.25 | 17.24 hbcsort | 0.31 | 0.47 | 1.88 | 1.68 | 0.30 | 3.18 | 1.69 | 3.49 | 3.72 | 2.19 | 4.85 nmsort | 0.38 | 0.45 | 1.76 | 1.74 | 0.36 | 2.22 | 1.78 | 3.49 | 3.58 | 2.27 | 4.83 fastSort | 0.54 | 0.62 | 0.87 | 0.96 | 0.64 | 1.23 | 2.33 | 1.27 | 2.50 | 1.23 | 5.15 -- = heap or stack overflow 1. |smooth |smooth |smooth | fastSort |smooth | fastSort | hbcsort | fastSort | fastSort | fastSort |nmsort 2. | hbcsort |nmsort | splay | Jon's | hbcsort |nmsort | nmsort | pairing |smooth | hbcsort | hbcsort 3. |nmsort | hbcsort | fastSort | hbcsort |nmsort | splay | fastSort | Jon's | Jon's | splay | fastSort 4. | fastSort | fastSort | Jon's |nmsort | fastSort | pairing | smooth | splay |nmsort |nmsort | Jon's 5. | splay | splay |nmsort | splay | splay | Jon's | Jon's | hbcsort | hbcsort | pairing | pairing 6. | Jon's | Jon's | hbcsort | bottom-up | pairing | hbcsort | pairing |nmsort | pairing | Jon's | splay 7. | pairing | pairing | bottom-up | pairing | bottom-up |smooth | splay |smooth | splay |smooth | braun 8. | bottom-up | bottom-up | pairing |smooth | Jon's | merge | bottom-up | bottom-up | merge | merge | merge 9. | merge | merge | merge | merge | merge | bottom-up | merge | merge | bottom-up | bottom-up | bottom-up 10. | braun | braun | braun | braun | braun | braun | braun | braun | braun | braun | heap 11. | heap | heap | heap | heap | heap | heap | heap | heap | heap | heap |smooth Times were taken on a loaded Sun Ultra-1 Sparcstation (run time options as above, *minimum* out of five runs). The `merge sorts' are in front with pairing sort following hard on their heels. However, this is a statement which is `ghc'-specific! Roughly speaking, `ghc' does not like classes, and prefers higher-order functions instead. If we increase the size of the input data 500.000 | < |<= | > |>= |== | 1 2* | 1..100* | 2 1* | 100..1* | 1 2 2 1* |random Jon's | 20.15 | 29.03 | 20.18 | 19.92 | 20.49 | 27.52 | 30.98 | 27.48 | 30.96 | 25.26 | 80.36 hbcsort | 2.67 | 7.00 | 44.54 | 26.34 |
Re: Filehandeling with Haskell
Hi Roland, > However my question is: How to do a little bit more complex IO: > Assume I have a file called 'filenames.txt' that contains a > list of filenames eg: > file1.txt > file2.txt > file3.txt > > I now want to write a simple program, that prints out the first > line of every file mentioned in 'filenames.txt'. here we are ... > module Main > where > printFirstLineOf :: FilePath -> IO () > printFirstLineOf filePath > = do contents <- readFile filePath > putStrLn ((lines contents ++ [""])!!0) > main :: IO () > main = do contents <- readFile "filenames.txt" > mapM_ printFirstLineOf (lines contents) The function `printFirstLineOf' prints the first line of the given file (no error handling). If the file is empty its prints `'. The predefined function `mapM_ f x' applies `f' to every element in `x' and sequences the `IO' actions. Ralf P.S.: Your code does not work since `processSingleFile' does `IO' but the type pretends it's a pure function. > processSingleFile :: String -> String > processSingleFile s = > do > inh <- openFile s ReadMode > cont <- hGetContents inh > return (head (lines cont))
Re: heap sort or the wonder of abstraction
Lennart wrote > Well, I'm a sucker for a benchmark so I ran all of these with hbc. > I also added the smooth merge sort that comes with hbc. > ... > As you can see there is no clear winner, but I see no real reason > to change the sort that comes with hbc to something else at this > moment. You are right, I should clarify that the recommendations are ghc specific (in the next version ;-). > > sortHbc :: (Ord a) => [a] -> [a] > > sortHbc [] = [] > > sortHbc (x:xs) = msort (upSeq xs [x]) > > > > upSeq [] xs = [reverse xs] > > upSeq (y:ys) xxs@(x:xs) = > > if x <= y then > > upSeq ys (y:xxs) > > else > > reverse xxs : upSeq ys [y] > > > > msort [xs] = xs > > msort xss = msort (mergePairs xss) > > > > mergePairs (xs:ys:xss) = merge xs ys : mergePairs xss > > mergePairs xss = xss > > > > merge xxs@(x:xs) yys@(y:ys) = > > if x <= y then > > x:merge xs yys > > else > > y:merge xxs ys > > merge [] yys = yys > > merge xxs[] = xxs That's a first-order version of the smooth bottom-up mergesort (which I did not include in the timings because the difference to the top-down variant was not significant). `sortHbc' is probably slightly faster than `smoothMergeSort' because its first-order? NB Bottom-up mergsort was my previous favourite ;-). Your version has the slight drawback that it uses only increasing sequences. > BTW, I don't think the test program does the right thing. It prints > the last element of the sorted list, but there is nothing that > says that computing this forces the list to be completely sorted. > When I test sort routines I always do something like printing the > sum of the sorted list. Hmm. I think this does not apply to the examples I gave but you are right, it could happen. cheatSort x = [ nth i x | i <- [1 .. length x] ] where `nth i x' computes the ith smallest element of x. > Furthermore (while I'm in a whining mode :-), taking the median > of several runs is not the accepted wisdom. You should take the > minimum of several runs. Fixed. Ralf
Splay sort
> Ralf, could I > ask you to run my code below through your experiments (I don't have > easy access to anything but hugs at the moment)? Here we are ... 5 | < |<= | > |>= |== | 1 2* | 1..100* | 2 1* | 100..1* | 1 2 2 1* |random merge | 1.29 | 3.65 | 1.27 | 2.76 | 1.30 | 1.78 | 2.85 | 1.84 | 2.85 | 1.69 | 7.59 bottom-up | 0.96 | 2.24 | 0.87 | 2.04 | 0.96 | 1.77 | 2.86 | 1.78 | 2.86 | 1.57 | 7.89 heap | 8.87 |oo | 8.88 |oo | 6.17 | 7.44 | 8.76 | 7.31 | 8.62 | 7.13 | 9.82 pairing | 0.53 | 1.54 | 0.70 | 1.88 | 0.52 | 1.19 | 1.72 | 1.22 | 1.92 | 1.13 | 3.58 Jon's | 0.48 | 1.14 | 0.52 | 1.19 | 1.12 | 1.43 | 1.72 | 1.44 | 1.64 | 1.39 | 3.79 braun | 8.74 | 22.02 | 6.94 | 21.91 | 2.78 | 5.18 | 6.37 | 5.06 | 6.25 | 5.13 | 9.37 smooth | 0.13 | 0.28 | 0.13 | 2.98 | 0.11 | 1.60 | 1.39 | 1.57 | 1.29 | 1.55 | 7.67 splay | 0.39 | 0.81 | 0.37 | 1.87 | 0.40 | 0.85 | 2.23 | 0.84 | 1.75 | 0.76 | 5.35 oo = heap or stack overflow 1. |smooth |smooth |smooth | Jon's |smooth | splay | smooth | splay |smooth | splay | pairing 2. | splay | splay | splay | splay | splay | pairing | pairing | pairing | Jon's | pairing | Jon's 3. | Jon's | Jon's | Jon's | pairing | pairing | Jon's | Jon's | Jon's | splay | Jon's | splay 4. | pairing | pairing | pairing | bottom-up | bottom-up |smooth | splay |smooth | pairing |smooth | merge 5. | bottom-up | bottom-up | bottom-up | merge | Jon's | bottom-up | merge | bottom-up | merge | bottom-up |smooth 6. | merge | merge | merge |smooth | merge | merge | bottom-up | merge | bottom-up | merge | bottom-up 7. | braun | braun | braun | braun | braun | braun | braun | braun | braun | braun | braun 8. | heap |(heap) | heap |(heap) | heap | heap | heap | heap | heap | heap | heap Times were taken on a *loaded* Sun Ultra-1 Sparcstation (run time options -K32M -H32M, *minimum* out of five runs). I incorporated Lennart's suggestion to `print the sum of the sorted list' as well. Splay trees perform quite well; second place? I am a bit sceptical about their ability to adopt to presorted data. You said: (In fact, it has been conjectured that splaySort is optimal with respect to any reasonable notion of "presortedness".[2]) The non-strictly decreasing sequence (>=) seems to be a hard nut to crack. Look at the following table ... 10 | < |<= | > |>= |== | 1 2* | 1..100* | 2 1* | 100..1* | 1 2 2 1* |random merge | 3.50 | 8.80 | 2.77 | 8.95 | 3.00 | 6.53 | 13.10 | 6.52 | 12.56 | 6.49 |oo bottom-up | 2.18 | 8.41 | 2.11 | 7.83 | 2.27 | 6.56 | 13.03 | 6.57 | 12.61 | 6.60 |oo heap |oo |oo |oo |oo | 21.91 |oo | oo |oo |oo |oo |oo pairing | 1.45 | 3.48 | 2.30 | 7.50 | 1.56 | 2.54 | 4.07 | 2.46 | 4.54 | 2.51 | 11.15 Jon's | 1.19 | 3.00 | 1.14 | 3.14 | 2.21 | 3.00 | 3.58 | 2.96 | 3.60 | 2.87 | 8.56 braun | 26.33 |oo | 22.21 |oo | 7.80 | 14.71 | 21.17 | 14.74 | 21.08 | 14.73 | 23.67 smooth | 0.30 | 0.62 | 0.27 | 7.70 | 0.28 | 4.30 | 3.37 | 4.33 | 3.25 | 4.29 |oo splay | 0.74 | 3.59 | 0.74 | 11.65 | 0.77 | 2.43 | 9.01 | 3.19 | 6.17 | 2.21 | 17.06 1. |smooth |smooth |smooth | Jon's |smooth | splay | smooth | pairing |smooth | splay | Jon's 2. | splay | Jon's | splay | pairing | splay | pairing | Jon's | Jon's | Jon's | pairing | pairing 3. | Jon's | pairing | Jon's |smooth | pairing | Jon's | pairing | splay | pairing | Jon's | splay 4. | pairing | splay | botto
Re: heap sort or the wonder of abstraction
d by ... Practitioners are probably surprised to learn that `pairingSort' is the algorithm of choice for sorting. Any objections to this recommendation? I was surprised to see that it performs so well: sorting 50.000 Int's in roughly three seconds and 100.000 Int's in roughly nine seconds is quite acceptable. A. Appendix ~~~ Here is yet another colleague of `foldr' and `foldl': `foldm' constructs a balanced expression tree. > foldm :: (a -> a -> a) -> a -> [a] -> a > foldm (*) e []= e > foldm (*) e x = fst (rec (length x) x) > where rec 1 (a:x) = (a, x) > rec n x = (a * b, z) > where m = n `div` 2 > (a, y)= rec (n - m) x > (b, z)= rec m y Jon's `treefold'. In a sense `foldm' works top-down and `treefold' works bottom-up. > treefold :: (a -> a -> a) -> a -> [a] -> a > treefold (*) e [] = e > treefold (*) e [a]= a > treefold (*) e (a:b:x)= treefold (*) e (a * b : pairfold (*) x) > pairfold :: (a -> a -> a) -> [a] -> [a] > pairfold (*) (a:b:x) = a * b : pairfold (*) x > pairfold (*) x= x -- here `x' will have fewer than two Note that `foldm' and `treefold' construct different trees: `foldm' returns a Braun tree while `treefold' returns a tree of the form t1 * (t2 * (.. (tn-1 * tn) ..)) where the ti's are complete binary trees in decreasing size. The size of the trees corresponds to the binary decomposition of the input length. The random-number generator which is stolen from the `hbc'-library. > random2Ints :: Int -> Int -> [Int] > random2Ints s1 s2 > | s1 < 1 || s1 > 2147483562 = error "random2Ints: Bad first seed." > | s2 < 1 || s2 > 2147483398 = error "random2Ints: Bad second seed." > | otherwise = rands s1 s2 > rands :: Int -> Int -> [Int] > rands s1 s2 > | z < 1 = z + 2147483562 : rands s1'' s2'' > | otherwise = z : rands s1'' s2'' > where k = s1 `div` 53668 > s1' = 40014 * (s1 - k * 53668) - k * 12211 > s1'' | s1' < 0 = s1' + 2147483563 >| otherwise= s1' > k' = s2 `div` 52774 > s2' = 40692 * (s2 - k' * 52774) - k' * 3791 > s2'' | s2' < 0 = s2' + 2147483399 >| otherwise= s2' > z = s1'' - s2'' Some auxiliary functions. > copy :: [a] -> [a] > copy = concat . repeat > interleave:: [a] -> [a] -> [a] > interleave [] y = y > interleave (a:x) y= a : interleave y x References ~~ [1] Richard Bird and Philip Wadler. "Introduction to Functional Programming", 1988, Prentice-Hall, Series in Computer Science [2] Lawrence C Paulson. "ML for the Working Programmer", second edition, 1996, Cambridge University Press [3] Chris Okasaki. "Purely Functional Data Structures", PhD thesis, School of Computer Science, Carnegie Mellon University,1996, CMU-CS-96-177 [4] Ralf Hinze."Einf"uhrung in die funktionale Programmierung mit Miranda", 1992, Teubner Verlag [5] Michael L Fredman, Robert Sedgewick, Daniel D Sleator and Robert E Tarjan. "The pairing heap: A new form of self-adjusting heap" Algorithmica 1(1):111-129, 1986. [6] Chris Okasaki, "Functional Data Structures", The Second International Summer School on Advanced Functional Programming Techniques, 1996, LNCS 1129 [7] David J King, "Functional Programming and Graph Algorithms", PhD thesis, Department of Computer Science, University of Glasgow, 1996 [8] Richard S. Bird, "Functional algorithm design", Science of Computer Programming, 26 (1996), 15-31
Is Standard Haskell a serious language?
John Hughes writes > (...) > encountered all too many students with the impression that functional > languages are OK for toy programs, but for real work you need > C/C++/Java/whatever. They can easily get that impression, paradoxically, > because of the success we functional programmers have had in introducing > functional languages early in the curriculum! Students believe functional > languages are good for toy programs because they learned them when they could > only write toy programs. If they gradually discover that, in fact, the very > language they have learned is also used for very serious applications then > there's a chance of countering that impression. If instead they discover that > they were quite right, the language they have learned is considered a toy even > by functional language researchers, then I don't think we have much chance. So > personally I am dead against designing a `Noddy Haskell' which is clean enough > for teaching; let Standard Haskell be clean instead! In essence this sounds to me like `let us design a serious language which is simple to teach *and* which is worth learning'. I strongly support this point of view. The goals of the Standard Haskell committee, however, only reflect the aim of simplifying the current Haskell design. [As Will Partain puts it `The "make it easy for students" people are running amok (...)']. While simplicity is certainly a desirable goal it is not nearly as important as developing a serious language. To turn Haskell into a serious language, several *extensions* are absolutely necessary: o Haskell's type system must be improved: multiple parameter type classes are a must (*). It is currently not possible to develop a *clean* library of data structures (collection classes) and computational structures (monad transformers). A well-developed library would certainly contribute to Haskell's seriousity. [This point has already been made, I just wanted to stress its importance.] (*) One should even consider to adopt each of the recommended extensions in the Haskell workshop paper "Type classes: an exploration of the design space". o Lazy state threads with mutable variables and mutable arrays are a must. There are a couple of algorithms and data structures for which no purely functional solution is known to exist. Efficiency is at a premium, so students will certainly classify Haskell as a toy language if the complexity gap cannot be bridged by means of an imperative sublanguage. [Furthermore it is not possible to develop an *efficient* library of data structures.] If the adoption of lazy state threads means that explicit quantification is also desirable, adopt it too! o Perhaps primitives for concurrency should be standardized, but I'm not an expert here. A language which does not support GUI programming is probably considered toy, as well. o Types such as Packed Strings or Packed Booleans (ie bitlist) are missing in the Standard Library. Could one otherwise convince students that Haskell is not an academic playground? I believe not. Ralf Hinze
Re: A new view of guards
Just wanted to add two minor points to the discussion. Beforehand let me say that I *really* like Simon's proposal [despite the various objections]. Mainly, because it's a small upwards compatible change with a considerable gain. Going back to Simon's first `clunky' example. > Now consider the following definition: > >clunky env var1 var2 | ok1 && ok2 = val1 + val2 > | otherwise = var1 + var2 > where > m1 = lookup env var1 > m2 = lookup env var2 > ok1 = maybeToBool m1 > ok2 = maybeToBool m2 > val1 = expectJust m1 > val2 = expectJust m2 As a (partial) solution I would suggest to use a simple case expression involving pairs. [I have not seen this one before, but in my humble opinion it is the most natural solution in 1.4]. clunky env var1 var2 = case (lookup env var1, lookup env var2) of (Just val1, Just val2)-> val1 + val2 _ -> ... It scales up nicely when more than three lookups are involved. Of course, it does not work if `clunky' consists of more than one equation and the one above is expected to `fail'. [It is debatable, however, whether it is good programming style to use failing equations. After all that's what we tell our students: Use whenever possible disjunct and exhaustive patterns to separate cases.] The second point concerns nested guard expressions which I find rather attractive for the following reason: guards allow to shift nested conditionals from the rhs to the lhs of an equation. Think of applying the following transformation: lhs = if b1 then e1 else if b2 then e2 ... else if bn then en else e --> lhs | b1 = e1 | b2 = e2 ... | bn = en | otherwise = e But it may well be the case that one of the ei's also involves an if-then-else conditonal which I would like to get rid of using the above transformation: The result are nested guards on the left hand side. Currently, I must mix guards and top-level if-then-elses which I'm not particularly fond of. Here is a real world ;-) example taken almost verbatim from ghc'c FiniteMap module which implements Adam's balanced trees. mkBalBranch l a r | sl + sr < 2 = mkBranch l a r | sl*ratio < sr = case r of Branch _ rl _ rr | size rl < 2 * size rr -> singleL l a r | otherwise -> doubleL l a r | sr*ratio < sl = case l of Branch _ ll _ lr | size lr < 2 * size ll -> singleR l a r | otherwise -> doubleR l a r | otherwise = mkBranch l a r where sl = size l sr = size r Note the use of case expression to handle the subcases; for that purpose irrefutable patterns were once invented. Here we are: mkBalBranch l@(~Branch _ rl _ rr) a r@(~Branch _ ll _ lr) but now we are forced to use an if-then-else for both of the subcases. Using nested guards we arrive at mkBalBranch l@(~Branch _ rl _ rr) a r@(~Branch _ ll _ lr) | sl + sr < 2 = mkBranch l a r | sl*ratio < sr | size rl < 2 * size rr = singleL l a r | otherwise = doubleL l a r | sr*ratio < sl | size lr < 2 * size ll = singleR l a r | otherwise = doubleR l a r | otherwise = mkBranch l a r where sl = size l sr = size r which exposes the different cases quite clearly. Regards, Ralf
Re: Monad transformers via single-parameter classes?
It seems everybody is playing around with monads and monad transformers
these days. I tried to `simplify' the multiple constructor classes a
few days ago ;-). `State' worked as you described it, but I encountered
problems with SML-like exception handling:
> class Monad m => ExcMonad e m where
> raise :: e -> m a
> handle:: m a -> (e -> m a) -> m a
> instance Functor (Either a) where
> map f (Right a) = Right (f a)
> map f (Left a) = Left a
> instance Monad (Either a) where
> Left a >>= k = Left a
> Right a >>= k = k a
> return= Right
> instance ExcMonad a (Either a) where
> raise = Left
> Left a `handle` h= h a
> Right a `handle` h= Right a
I don't like the strings-only exception classes, so `ExcMonad' is
parameterized with the type of exceptions. Now, when I simplify the
class definition to
> class Monad m => ExcMonad m where
> raise :: e -> m a
> handle:: m a -> (e -> m a) -> m a
> instance ExcMonad (Either a) where
> raise = Left
> Left a `handle` h= h a
> Right a `handle` h= Right a
`hbc' complains:
Errors:
"ExcMonad.lhs", line 0, [59] Bad restriction
b -> Either c c
of type
a -> Either a a
identified tyvars
in ((\AA2990 -> Left AA2990{FARITY 1}))::c -> Either d d
in Either~a`raise
The class definition is too general: the type of exceptions must be
the fixed since `raise' and `handle' interact. That's in contrast with
a state monad: There is no reason why the type of the state should not
change.
Admittingly, I was a bit disappointed to see that Haskell 1.3 does not
allow for multiple parameter type classes. Most of the constructions to
be found in literature (lifting, composing etc) seem to require this
feature. Take for example lifting:
> class (Monad m, Monad (t m)) => MonadT t m where
> lift :: m a -> t m a
So Haskell 1.3 allows to play with monads but not with monad
transformers. Sigh.
Ralf
