Re: [Haskell-cafe] Help with lhs2TeX
Hi Dominic,
Hi, I wonder if someone could point out what I am doing wrong. My
understanding was that I should be able to create a .lhs file and run it
e.g. with ghci and then use lhs2TeX to create a nice .pdf file, all from
the same source. I can produce nice slides but unfortunately the .lhs
does compile because of the special symbols I wish to use. So presumably
I need to pre-process my file before submitting to ghci. However, I was
unable to find any information about this in the excellent guide. For
example:
\documentclass{beamer}
%include polycode.fmt
%format m_ = \mu
%format ^ =
%format inv(a) = a^^\circ
%format in_ = in
\begin{document}
\title{Some Notes on Category Theory with Some Applications to Computer
Science}
\author{Dominic Steinitz}
\begin{frame}
\frametitle{Haskell Example: Total}
Initial algebras can be defined as follows:
\begin{code}
newtype m_^f = In {inv(in_) :: f (m_^f )}
\end{code}
\end{frame}
\end{document}
produces a nice slide but does not compile.
If I change the offending line to
newtype Mu f = In {in_ :: f (Mu f)}
then all is well but the slide does not look as nice
the basic approach (originally) is to have an executable Haskell program
so that you can typecheck it. Then you add some %format directives to make
it look nice, eg.
%format Mu f = \mu f
%format in_ = in^\circ
should do the job.
Hth, Ralf
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Mysterious factorial
fact2 is O(log n) while fact is O(n). fact2 is partitioning the problem. But fact2 sparks off two recursive calls. If we assume that multiplication is a constant-time operations, both algorithms have the same asymptotic running time (try a version that operates on Ints). For Integers, this assumption is, of course, false ... Cheers, Ralf On Wed, Dec 30, 2009 at 08:57, Artyom Kazak artyom.ka...@gmail.com wrote: Why fact2 is quicker than fact?! fact2 :: Integer - Integer fact2 x = f x y where f n e | n 2 = 1 | e == 0 = n * (n - 1) | e 0 = (f n (e `div` 2)) * (f (n - (e * 2)) (e `div` 2)) y = 2 ^ (truncate (log (fromInteger x) / log 2)) fact :: Integer - Integer fact 1 = 1 fact n = n * fact (n - 1) I tried to write tail-recursive fact, fact as product [1..n] - fact2 is quicker! fact2 100 == fact 100 - I tested. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Mysterious factorial
fact2 sparks 2*n multiplications for every (n^2) factors fact sparks n multiplications for every n factors Okay, let's count: data Tree a = Leaf a | Fork (Tree a) (Tree a) deriving (Show) fact 1 = Leaf 1 fact n = Leaf n `Fork` fact (n - 1) fact2 x = f x y where f n e | n 2 = Leaf 1 | e == 0 = Leaf n `Fork` Leaf (n - 1) | e 0 = (f n (e `div` 2)) `Fork` (f (n - (e * 2)) (e `div` 2)) y = 2 ^ (truncate (log (fromInteger x) / log 2)) size (Leaf a) = 0 size (Fork l r) = 1 + size l + size r The code now creates a binary tree (instead of performing a multiplication). Main size (fact 100) 99 Main size (fact2 100) 108 Convinced? Cheers, Ralf ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Mysterious factorial
As an aside, in one of my libraries I have a combinator for folding a list in a binary-subdivision scheme. foldm :: (a - a - a) - a - [a] - a foldm (*) e x | null x= e | otherwise = fst (rec (length x) x) where rec 1 (a : as)= (a, as) rec n as = (a1 * a2, as2) where m = n `div` 2 (a1, as1) = rec (n - m) as (a2, as2) = rec m as1 Then factorial can be defined more succinctly factorial n = foldm (*) 1 [1 .. n] Cheers, Ralf ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Mysterious factorial
I would use: foldm :: Monoid m = [m] - m Which is just a better implementation of mconcat / fold. The reason I prefer this interface is that foldm has a precondition in order to have a simple semantics: the operator you're giving it has to be associative. I like to use typeclasses to express laws. That's a valid point. Unfortunately, Haskell is not Coq, so there is no guarantee that the monoid laws are actually satisfied. And using a type-class has the downside that you can have only one instance per type. Maybe, you want to use both `foldm (+) 0' and `foldm (*) 1'. So the bottom-line is that you should have both versions. Cheers, Ralf ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Applicative and Monad transformers
Hi Jeremy,
I have seen it said that all Monads are Applicative Functors because
you can just do:
instance (Monad f, Applicative f) = Applicative (ReaderT r f) where
pure = return
(*) = ap
However, that instance for ReaderT does not exhibit the properties I
was hoping for.
OK, let's calculate. Here are the necessary definitions for the reader
monad (not the monad transformer).
m = k = \ x - k (m x) x
u * v = \ x - (u x) (v x)
return a = pure a = \ x - a
So, * is the S combinator and pure is the K combinator.
u = \ f - v = \ a - return (f a)
= { definition of = }
\ x - (\ f - v = \ a - return (f a)) (u x) x
= { beta }
\ x - (v = \ a - return ((u x) a)) x
= { definition of = }
\ x - (\ a - return ((u x) a)) (v x) x
= { beta }
\ x - return ((u x) (v x)) x
= { definition of return }
\ x - (u x) (v x)
= { definition of * }
u * v
Yes, both definitions are, in fact, equal.
So, what went wrong in your program? Observe that the first instance
declaration can be simplified to
instance (Monad f) = Applicative (ReaderT r f) where
pure = return
(*) = ap
which is suspicious.
Hope this helps, Ralf
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell] Call for Contributions - HCA 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
Re: [Haskell-cafe] Re: Functional programming for processing of largeraster images
Am Mittwoch 21 Juni 2006 21:30 schrieb Brian Hulley: Perhaps laziness is more foundational, in that you can write if2 c x y = if c then x else y However: 1) What's the advantage of being able to define if2? Well, you can easily define you own control structures (when, unless etc). This feature is wildly used in combinator libraries. Also, in a non-strict language recursive definitions are not limited to function types. Users of parser combinators heavily rely on this feature. Just try to define/use parsing combinators ins a strict language. The problem with eager evaluation is that it is too eager (expressions are sometimes evaluated too early) just as the problem with lazy evaluation is that it is too lazy (evaluations sometimes happen too late). Cheers, Ralf ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[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
GADTs and type synonyms
Another GADT `bug report': type synonyms are not unfolded when checking the signature of the data constructors: given type Hello a = a - a data World :: * where Msg :: Hello World GHC reports GADT.lhs:2:1: Data constructor `Msg' returns type `Hello' instead of its parent type When checking the data constructor: Msg In the data type declaration for `World' Applies to both version 6.4.1 and 6.5. Cheers, Ralf ___ Glasgow-haskell-bugs mailing list Glasgow-haskell-bugs@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: [Haskell-cafe] Arrows for invertible programming: Notation question
What does this mean and how do I make it compile?
mapl{|a, b|arr|} :: (mapl{|a, b|arr|}, ArrowChoice arr, BiArrow arr) = arr a
b
It's Generic Haskell source code, see
http://www.generic-haskell.org/
Generic Haskell is an extension of Haskell that supports generic programming.
Cheers, Ralf
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Arrows for invertible programming: Notation question
Is this something that can be compiled with GHC right now? I noticed - fgenerics but I think it does something else entirely. GH is a pre-compiler that takes GH code to Haskell code, so this is a two-step process. -fgenerics turns derivable type classes on (see Derivable type classes, Ralf Hinze and Simon Peyton Jones, Haskell Workshop 2000, pp94-105). The two are different but related ... Cheers, Ralf ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] IO
Interesting discussion ...
I don't think it is necessary/desirable to relegate IO to `chapter 14'.
First of all, IO is handled differently in Haskell as the language
designers quite successfully resisted the temptation of impurity.
However, you don't have to understand the full implications of
IO to be able to use it (like you don't have to know the full English
grammar to be able to speak English). I typically cover IO very early
in a Haskell course and then again in `chapter 14' after a discussion
of monads. (To motivate the need for a special treatment of IO, I often
ask the students to put themselves into the position of a language
designer who tries to add IO to a purely functional language.)
So why is there a special `IO' type? The type serves to distinguish
between values and effectful computations: `String' is the type of
strings, `IO String' is the type of computations that deliver a
string. This is why the `do' notation uses `-' instead of `='.
ask :: String - IO String
ask question = do { putStrLn question;
answer - getLine;
putStrLn Thanks!;
return answer }
Here, `answer' of type `String' is the result of the effectful
computation `getLine' of type `IO String'. I think IO can be
treated on this level, just using the `do'-notation (it is not
necessary to explain that the do-notations is merely syntactic
sugar for `=' which involves higher-order functions).
One thing that is important to stress, however, is that `-' is
a binder: the variable on the lhs is *bound* to value delivered
by the rhs. In other words, `-' introduces a variable (it does
not assign a value to a store). Consequently, in
do { a - m1; a - m2; ... }
the second occurrence of `a' shadows the first occurrence.
It is useful to think of `IO' as a `description' of an effectful
computation (it is very much like a TODO list; the list describes
actions, which may or may not be executed). This is why something
of type `IO a' is also a value: it may be stored in a data structure
or passed to a function. This means you can program you own control
structures:
data IOTree a = Done (IO a)
| Choice (IO Bool) (IOTree a) (IOTree a)
execute :: IOTree a - IO a
execute (Done action)
= do { action }
execute (Choice action left right)
= do { b - action;
if b then do { execute left }
else do { execute right } }
Now, if IO is only a `description' of an IO action, when is the IO action
actually executed? Exactly when `main' is called: only the TODO list
that is bound to `main' is executed. Consider
main = do { head [putStrLn hello world, putStrLn too lazy] }
HTH, Ralf
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Strictness annotations on type parameters
It's hard to avoid the feeling that one ought to be able to say
something useful about strictness in the types but it's swampy
territory, and hard to get right.
Fortunately, it's easy to dry up the `swampy territory'. The type
`Contract' below models strictness requirements. The function
`assert' implements them (`assert c' is a so-called projection).
Feel free to experiment with different designs ...
{-# OPTIONS -fglasgow-exts #-}
infixr :-
data Contract :: * - * where
Id :: Contract a
(:-) :: Contract a - Contract b - Contract (a - b)
(:=) :: Contract a - Contract b - Contract (a - b)
List:: Contract a - Contract [a]
SList :: Contract a - Contract [a]
assert :: Contract a - (a - a)
assert Id = id
assert (c1 :- c2) = \ f - assert c2 . f . assert c1
assert (c1 := c2) = \ f x - x `seq` (assert c2 . f . assert c1) x
assert (List c) = map (assert c)
assert (SList c)= \ xs - eval xs `seq` map (assert c) xs
eval []= []
eval (a : as) = a `seq` eval as
Some test data.
evens [] = []
evens [a] = [a]
evens (a1 : a2 : as) = evens as
assert (Id :- Id) (const 1) undefined
assert (Id := Id) (const 1) undefined
assert (Id := Id) (sum . evens) [1, undefined]
assert (SList Id := Id) (sum . evens) [1, undefined]
Cheers, Ralf
PS: Just in case you wonder, the code has been adopted from a recent
paper on contracts (see my homepage).
___
Glasgow-haskell-users mailing list
Glasgow-haskell-users@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
GADTs: malformed constructor signature
Rather unituitively, GHC allows
{-# OPTIONS -fglasgow-exts #-}
data T :: * where
C :: Int - Int - T
but not
data T :: * where
C :: Int - (Int - T)
Sometimes, I like to parenthesize the result type for emphasis.
Cheers, Ralf
___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
[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-cafe] Regular Expressions without GADTs
The code seems a bit simpler, too. Do you really think so? To me replacing a GADT by class and instance declarations seems the wrong way round. We should not forget that the DT in GADT stands for `data type'. One could certainly argue that the gist of functional programming is to define a collection of data types and functions that operate on these types. The fact that with GADTs constructors can have more general types just allows us to use the functional design pattern more often (freeing us from the need or temptation to resort to type class hackery with multiple parameter type classes, undecidable instances, functional dependencies etc). Cheers, Ralf ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Estonia and GADT
Hi Bulat, 2) they all say that GADT is great, but i personally don't feel GADTs. can anyone write a paper about it for beginners like me, or may be just collect examples of using GADT in real programs? I wrote a book chapter on GADTs a while ago, called Fun with phantom types, see http://www.informatik.uni-bonn.de/~ralf/publications.html#B4 It's not aimed at beginners though. [Furthermore, the syntax for GADTs is a bit different.] Cheers, Ralf ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Newbie question on Haskell type
Hi Huong,
attached you find a small program for parsing values of various (data)
types. It uses a generalized algebraic data type for representing types
and a universal data type for representing values. The parser itself is
rather simple-minded: it builds on Haskell's ReadS type.
I don't know whether this is what you are after, but it was fun writing.
There are many opportunities for improvement: one could use a decent
combinator library for parsing; a type of dynamic values instead of a
universal type etc.
Here are some example calls:
Main parseAny 4711
[(ValInt 4711,)]
Main parseAny \4711\
[(ValString 4711,)]
Main parseAny [4711, 0]
[(ValList [ValInt 4711,ValInt 0],)]
Main parseAny [4711, 'a']
[(ValList [ValInt 4711,ValChar 'a'],)]
Main parseAny [\hello world\]
[(ValList [ValString hello world],)]
Note that parseAny even parses heterogenous lists.
Cheers, Ralf
---
{-# OPTIONS -fglasgow-exts #-}
data Type :: * - * where
Char:: Type Char
Int :: Type Int
List:: Type a - Type [a]
Value :: Type Value
string :: Type String
string = List Char
parse :: Type t - ReadS t
parse (Char) = reads
parse (Int)= reads
parse (List Char) = reads
parse (List a) = parseList (parse (a))
parse (Value) = parseAny
data Value
= ValCharChar
| ValInt Int
| ValString String
| ValList[Value]
deriving (Show)
parseAny
= ValChar $ parse Char
+ ValInt$ parse Int
+ ValString $ parse string
+ ValList $ parse (List Value)
Helper functions.
parseList parsea
= readParen False (\ s - [ xs | ([, t) - lex s, xs - parsel t ])
where parsel s = [ ([], t) | (], t) - lex s ]
++ [ (x : xs, u) | (x, t) - parsea s,
(xs, u) - parsel' t ]
parsel' s = [ ([], t) | (], t) - lex s ]
++ [ (x : xs, v) | (,, t) - lex s,
(x, u) - parsea t,
(xs, v) - parsel' u]
infix 8 $
infixr 6 +
(f $ p) s = [ (f a, t) | (a, t) - p s ]
(p + q) s = p s ++ q s
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: 6.4.1 release candidate testing
Please ignore last night's snapshot (3/8), something is broken. The message came in too late ;-). Anyway, 3/8 compiled fine (using 1/8) and it seems to work. Environment: patronus ghc-6.4.1.20050803 # uname -a Linux patronus 2.6.12-gentoo-r7 #1 Wed Aug 3 18:57:28 CEST 2005 x86_64 AMD Athlon(tm) 64 Processor 3000+ AuthenticAMD GNU/Linux BTW, I am especially thankful that ghci works again! Cheers, Ralf ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
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
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
can anybody tell me what the German translation of the word kind as used in type theory and especially in Haskell is? Wie wr's mit `Sorte', Ralf ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: Registerised x86_64 port: test version available
Hi Simon, this is just to let you know that I successfully compiled the lastest snapshot (ghc-6.4.20050308). Initial tests look promising. Thanks! Cheers, Ralf PS: Just curious: is the gcc route easier than the NCG? To me it seems much more fragile. ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: x86_64 port
My amd64 hardware arrived yesterday, shouldn't be too long before we have a registerised port of GHC, and possibly a native code generator... That would be great! I just assembled an amd64 box and I am mssing ghci badly. Let me know if I can be of any help (testing ..). Cheers, Ralf ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: [Haskell-cafe] special term describing f :: (Monad m) = (a - m b) ?
I can understand how calling this kind of function effectual makes sense in the magic IO monad, or perhaps even in the ST and State monads, because the term seems to imply side-effects. However, it is a misnomer for eg, the Error, List and Cont monads. It depends a bit on how wide you interpret the term effectfull. For me, exceptions or partiality (Error), non-determinisms or backtracking (List) and continuations (Cont) are certainly effects. Cheers, Ralf ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] special term describing f :: (Monad m) = (a - m b) ?
What is a function of the followning type called: f :: (Monad m) = (a - m b) Is there a special term describing such a function (a function into a monad)? It is often called a procedure or an effectful function (I assume that `a' and `b' are not meant to be universally quantified). I sometimes use a special arrow -| for this type. Cheers, Ralf ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Browsing RealWorld broken
Here is another one: the case for foreign declarations seems to miss in ghc/compiler/ghci/InteractiveUI.hs:showDecl: ./bin/ghci ___ ___ _ / _ \ /\ /\/ __(_) / /_\// /_/ / / | | GHC Interactive, version 6.3, for Haskell 98. / /_\\/ __ / /___| | http://www.haskell.org/ghc/ \/\/ /_/\/|_| Type :? for help. Loading package base ... linking ... done. Prelude :i GHC.Base.RealWorld *** Exception: ghci/InteractiveUI.hs:(505,0)-(555,49): Non-exhaustive patterns in function showDecl Well, it should be fairly obvious that you cannot browse the real world. ___ Glasgow-haskell-bugs mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: __stginit_Int_
Loading package fmp ... linking ... /home/ralf/Software/FuncMP/fmp.o: unknown symbol `__stginit_Int_' ghc-6.2: panic! (the `impossible' happened, GHC version 6.2): can't load package `fmp' Try adding -package haskell98 to GHC's options or use the Data.Int module instead of module Int. Thanks for the work-around(?). Adding -package haskell98 works if it listed after -package fmp. basilisk /home/ralf ghci -package haskell98 -package fmp ___ ___ _ / _ \ /\ /\/ __(_) / /_\// /_/ / / | | GHC Interactive, version 6.2, for Haskell 98. / /_\\/ __ / /___| | http://www.haskell.org/ghc/ \/\/ /_/\/|_| Type :? for help. Loading package base ... linking ... done. Loading package lang ... linking ... done. Loading package fmp ... linking ... /home/ralf/Software/FuncMP/fmp.o: unknown symbol `__stginit_Int_' ghc-6.2: panic! (the `impossible' happened, GHC version 6.2): can't load package `fmp' Please report it as a compiler bug to [EMAIL PROTECTED], or http://sourceforge.net/projects/ghc/. basilisk /home/ralf ghci -package fmp -package haskell98 ___ ___ _ / _ \ /\ /\/ __(_) / /_\// /_/ / / | | GHC Interactive, version 6.2, for Haskell 98. / /_\\/ __ / /___| | http://www.haskell.org/ghc/ \/\/ /_/\/|_| Type :? for help. Loading package base ... linking ... done. Loading package haskell98 ... linking ... done. Loading package lang ... linking ... done. Loading package fmp ... linking ... done. ___ Glasgow-haskell-bugs mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: __stginit_Int_
Thanks for the work-around(?). Adding -package haskell98 works if it listed after -package fmp. It's not a workaround, it's just a missing dependency for your fmp package. Probably the right thing would be adding haskell98 to the package_deps field of your package description for fmp. Thanks for the clarification! Cheers, Ralf ___ Glasgow-haskell-bugs mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: Puzzle
Am Dienstag, 26. August 2003 05:54 schrieb Matt Harden: Cool! That leads me to this contraption: tricky= 0 : enigma tricky tricky enigma (k : ks) = (k :) . labyrinth (enigma ks) labyrinth f (k : _ : ks) = (k + 1) : f ks Figure out what `tricky' is, and what its relationship is to `unknown'. Well, `tricky' can be defined much simpler: tricky = [0 ..] \/ tricky where `\/' denotes ... (I leave this to the imagination of the reader). Cheers, Ralf ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Puzzle
| Seeing as its thst time of year again and everyone is posting their | homework, has anyone got any good puzzles to do? | I wouldn't mind having a go at something a bit tricky. Here is another one: figure out what `unknown' is. unknown = mysterious unknown mysterious ks = 0 : weird ks weird (k : ks)= (k + 1) : mysterious ks Cheers, Ralf ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
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
Predicativity
Dear Simon, dear Mark, I had a very cursory look at your Practical type inference for arbitrary-rank types paper. One thing that catched my attention was the remark about predicativity in Sec. 3.4. Recently, I posted a `bug report' to the glasgow-haskell-bugs mailing list complaining about GHC's type checker being very resource hungry, see http://haskell.org/pipermail/glasgow-haskell-bugs/2003-May/003258.html Here is the problem in a nutshell (`copy' is just identity): infixl 9 # f # x = f x copy = \ x - x foo = (copy # copy # copy # copy # copy # copy # copy # copy # copy # copy # copy # copy # copy # copy # copy # copy # copy # copy # copy # copy # copy # copy # copy # copy # copy # copy # copy # (+ 1)) (0 :: Int) GHC is not able to compile this program (Hugs and nhc98 are). Since the type system is predicative, the leftmost instance of `copy' is instantiated to (Int - Int)^27 where t^1 = t and t^(n+1) = t^n - t^n. The type explodes (using sharing t^n maybe represented in linear space, but sharing is impossible to maintain in a *pure* setting). Now, if we switch to an impredicatice system (in GHC we can simulate such a system using newtypes with embedded foralls), the problem disappears. If we redefine `#' and `copy' newtype Id = Id (forall a . a - a) Id f # x = f x copy = Id (\ x - x) the program compiles just fine. The leftmost instance of `copy' is now instantiated to the polytype `forall a . a - a' (written as `Id'). No type explosion! Coming back to the paper, it may be worth mentioning that predicativity has its drawbacks ... (I am still wondering why Hugs and nhc98 happily accept the first program.) Cheers, Ralf ___ Glasgow-haskell-bugs mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
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: 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: 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: 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: 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
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 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: Collecting values from Functors?
class FunctorM t where fmapM :: Monad m = (a - m b) - (t a - m (t b)) fmapM_ :: Monad m = (a - m b) - (t a - m ()) fmapM_ f t = fmapM f t return () The `fmapM' function is also known as a monadic map. It can be defined in a generic way for every Haskell data type. It's in the library of Generic Haskell (called mapMl): http://www.cs.uu.nl/research/projects/generic-haskell/ As an aside, gmap and friends won't fit the bill, as they work on types rather than functors. Cheers, Ralf ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
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: ANNOUNCE: GHC version 6.0
Compiling 6.0 from source fails with: ../../ghc/compiler/ghc-inplace -H16m -O -Wall -fffi -Iinclude '-#include HsOpenGL.h' -cpp -I/usr/X11R6/include -DCALLCONV=ccall '-DGET_PROC_ADDRESS=glXGetProcAddressARB' -package-name OpenGL -O -Rghc-timing -package base -split-objs-c Graphics/Rendering/OpenGL/GL/Extensions.hs -o Graphics/Rendering/OpenGL/GL/Extensions.o -ohi Graphics/Rendering/OpenGL/GL/Extensions.hi Graphics/Rendering/OpenGL/GL/Extensions.hs:42: parse error on input `glXGetProcAddressARB' ghc: 3261568 bytes, 2 GCs, 20548/20548 avg/max bytes residency (1 samples), 5M in use, 0.00 INIT (0.00 elapsed), 0.01 MUT (0.09 elapsed), 0.01 GC (0.03 elapsed) :ghc make[2]: *** [Graphics/Rendering/OpenGL/GL/Extensions.o] Fehler 1 make[1]: *** [all] Fehler 1 make[1]: Leaving directory `/var/tmp/portage/ghc-6.0/work/stage2-build/libraries' make: *** [build] Fehler 1 The following patch worked for me (but does it cure the problem?) irrwisch root # diff libraries/OpenGL/Graphics/Rendering/OpenGL/GL/Extensions.hs libraries/OpenGL/Graphics/Rendering/OpenGL/GL/Extensions.hs-orig 42c42 foreign import CALLCONV unsafe GET_PROC_ADDRESS :: --- foreign import CALLCONV unsafe GET_PROC_ADDRESS glXGetProcAddressARB :: Cheers, Ralf ___ Glasgow-haskell-bugs mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: GHC *is* resource hungry
I bet it's massive types. Translate the program into system F and see. (I remember this came up when looking at Okasaki's sequences of code combinators.) Ok. I didn't use System Fomega (no compiler at hand) but GHC's data types with locally quantified fields. Here is the original program (I added type signatures and swapped the argument of `leaf'). type CPS a = forall ans . (a - ans) - ans begin :: CPS (a - a) begin next = next id leaf :: Int - (Int - a) - CPS a leaf i k next = next (k i) fork :: (Int - a) - CPS (Int - Int - a) fork k next = next (\ t u - k (t + u)) end :: a - a end x = x main = print (begin fork fork fork fork fork fork fork fork fork fork (leaf 0) (leaf 0) (leaf 0) (leaf 0) (leaf 0) (leaf 0) (leaf 0) (leaf 0) (leaf 0) (leaf 0) (leaf 0) end) Still massive problems. Now, if I turn the `type' into a `newtype' declaration and insert a few identity functions (`CPS' and `#'), then GHC compiles the program like a charm. The charm of the original program is, of course, gone. newtype CPS a = CPS (forall ans . (a - ans) - ans) infixl 9 # CPS m # k = m k begin :: CPS (a - a) begin = CPS (\ next - next id) leaf :: Int - (Int - a) - CPS a leaf i k = CPS (\ next - next (k i)) fork :: (Int - a) - CPS (Int - Int - a) fork k = CPS (\ next - next (\ t u - k (t + u))) end :: a - a end x = x main = print (begin # fork # fork # fork # fork # fork # fork # fork # fork # fork # fork # leaf 0 # leaf 0 # leaf 0 # leaf 0 # leaf 0 # leaf 0 # leaf 0 # leaf 0 # leaf 0 # leaf 0 # leaf 0 # end) Maybe this helps to identify the source of the problem. Cheers, Ralf ___ Glasgow-haskell-bugs mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: ANNOUNCE: GHC version 6.0
Please report bugs using our SourceForge page at http://sourceforge.net/projects/ghc/ or send them to [EMAIL PROTECTED] Compiling 6.0 from source fails with: ../../ghc/compiler/ghc-inplace -H16m -O -Wall -fffi -Iinclude '-#include HsOpenGL.h' -cpp -I/usr/X11R6/include -DCALLCONV=ccall '-DGET_PROC_ADDRESS=glXGetProcAddressARB' -package-name OpenGL -O -Rghc-timing -package base -split-objs-c Graphics/Rendering/OpenGL/GL/Extensions.hs -o Graphics/Rendering/OpenGL/GL/Extensions.o -ohi Graphics/Rendering/OpenGL/GL/Extensions.hi Graphics/Rendering/OpenGL/GL/Extensions.hs:42: parse error on input `glXGetProcAddressARB' ghc: 3261568 bytes, 2 GCs, 20548/20548 avg/max bytes residency (1 samples), 5M in use, 0.00 INIT (0.00 elapsed), 0.01 MUT (0.09 elapsed), 0.01 GC (0.03 elapsed) :ghc make[2]: *** [Graphics/Rendering/OpenGL/GL/Extensions.o] Fehler 1 make[1]: *** [all] Fehler 1 make[1]: Leaving directory `/var/tmp/portage/ghc-6.0/work/stage2-build/libraries' make: *** [build] Fehler 1 Cheers, Ralf ___ Glasgow-haskell-bugs mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
GHC *is* resource hungry
Here is a harmless little program (no recursion, no data types) which GHC doesn't manage to compile (well, the kernel kills GHC after a while on a machine with generous 512MB of main memory and 1GB of swap space). begin next = next id leaf k i next = next (k i) fork k next = next (\ t u - k (t + u)) end x = x main = print (begin fork fork fork fork fork fork fork fork fork fork leaf 0 leaf 0 leaf 0 leaf 0 leaf 0 leaf 0 leaf 0 leaf 0 leaf 0 leaf 0 leaf 0 end) Both Hugs and nhc98 accept it almost immediately. Cheers, Ralf ___ Glasgow-haskell-bugs mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: GHC *is* resource hungry
I bet it's massive types. Translate the program into system F and see. (I remember this came up when looking at Okasaki's sequences of code combinators.) Your bet is most likely the correct one (yes, I peeked at Chris' HW2002 paper). GHC doesn't try to hash-cons types, because it usually doesn't matter, but I bet it does here. Would this be a major rewrite? [As an aside, a similiar problem showed up when generating conversion functions for generic representation types.] Cheers, Ralf | -Original Message- | From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On | Behalf Of Ralf Hinze | Sent: 28 May 2003 15:32 | To: [EMAIL PROTECTED] | Subject: GHC *is* resource hungry | | Here is a harmless little program (no recursion, no data types) | which GHC doesn't manage to compile (well, the kernel kills GHC | after a while on a machine with generous 512MB of main memory | and 1GB of swap space). | | begin next = next id | leaf k i next = next (k i) | fork k next = next (\ t u - k (t + u)) | end x = x | main = print (begin fork fork fork fork fork fork fork fork fork fork leaf 0 leaf 0 leaf 0 leaf 0 leaf 0 | leaf 0 leaf 0 leaf 0 leaf 0 leaf 0 leaf 0 end) | | Both Hugs and nhc98 accept it almost immediately. | | Cheers, Ralf | | ___ | Glasgow-haskell-bugs mailing list | [EMAIL PROTECTED] | http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs ___ Glasgow-haskell-bugs mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
n + k patterns
GHCi infers for fac 0 = 1 fac (n + 1) = (n + 1) * fac n the following type / _ \ /\ /\/ __(_) / /_\// /_/ / / | | GHC Interactive, version 5.04.2, for Haskell 98. / /_\\/ __ / /___| | http://www.haskell.org/ghc/ \/\/ /_/\/|_| Type :? for help. Loading package base ... linking ... done. Loading package haskell98 ... linking ... done. Compiling Main ( Fac.lhs, interpreted ) Ok, modules loaded: Main. *Main :t fac forall a. (Num a, Ord a) = a - a The Report, however, states that 3.17.2 Informal Semantics of Pattern Matching ... An n+k pattern can only be matched against a value in the class Integral. Cheers, Ralf ___ Glasgow-haskell-bugs mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
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
Re: Global variables?
Pavel G. Zhbanov wrote: Is it even possible to make a global variable in Haskell? If yes, how? The usual fudge is: import IORef import IOExts globalVar :: IORef Int globalVar = unsafePerformIO $ newIORef 0 However, beware of creating more than one global variable of the same type. If you enable optimisation, common subexpression elimination may result in both names referring to the same IORef. John Hughes wrote a nice pearl on the subject, see http://www.math.chalmers.se/~rjmh/Globals.ps Cheers, Ralf ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
build of ghc-5.05.20021118 fails
From time to time I try out one of the development snapshots. Does it make sense to report errors? Anyway, the the build of ghc-5.05.20021118 fails with the following error message ... ==fptools== make html - --no-print-directory -r; in /var/tmp/portage/ghc-5.05.20021118/work/stage3-build/ghc/docs/users_guide ../../../glafp-utils/docbook/db2html -d /var/tmp/portage/ghc-5.05.20021118/work/stage3-build/docs/fptools-both.dsl users_guide.sgml CATALOG file not set up; see installation guide for details. make[3]: *** [users_guide.html] Fehler 1 make[2]: *** [html] Fehler 1 make[1]: *** [html] Fehler 1 make: *** [html] Fehler 1 ___ Glasgow-haskell-bugs mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
ghc-5.05.20021109 build failure
Hi Folks, just to let you know: the (nightly) build of ghc-5.05.20021109 fails with ... ==fptools== make all -wr; in /var/tmp/portage/ghc-5.05.20021109/work/stage3-build/libraries/GLUT ../../ghc/compiler/ghc-inplace -ldl -Wall -fglasgow-exts -package OpenGL -Iinclude '-#include HsGLUT.h' -cpp -DCALLCONV=ccall -package-name GLUT -O -Rghc-timing -package base -package OpenGL-c Graphics/UI/GLUT/Constants.hs -o Graphics/UI/GLUT/Constants.o ghc: 53475036 bytes, 18 GCs, 1615048/2975660 avg/max bytes residency (3 samples), 9M in use, 0.02 INIT (0.01 elapsed), 0.72 MUT (3.22 elapsed), 0.38 GC (0.38 elapsed) :ghc ../../ghc/compiler/ghc-inplace -ldl -Wall -fglasgow-exts -package OpenGL -Iinclude '-#include HsGLUT.h' -cpp -DCALLCONV=ccall -package-name GLUT -O -Rghc-timing -package base -package OpenGL-c Graphics/UI/GLUT/Initialization.hs -o Graphics/UI/GLUT/Initialization.o ghc: 189538924 bytes, 510 GCs, 4522708/8117960 avg/max bytes residency (6 samples), 21M in use, 0.01 INIT (0.02 elapsed), 2.82 MUT (13.41 elapsed), 2.01 GC (2.08 elapsed) :ghc ../../ghc/compiler/ghc-inplace -ldl -Wall -fglasgow-exts -package OpenGL -Iinclude '-#include HsGLUT.h' -cpp -DCALLCONV=ccall -package-name GLUT -O -Rghc-timing -package base -package OpenGL-c Graphics/UI/GLUT/Window.hs -o Graphics/UI/GLUT/Window.o Graphics/UI/GLUT/Window.hs:65: No instance for (Ord GHC.Int.Int32) arising from the instance declaration at Graphics/UI/GLUT/Window.hs:65 In the instance declaration for `Ord Window' ghc: 49383456 bytes, 20 GCs, 2054532/3997348 avg/max bytes residency (3 samples), 8M in use, 0.02 INIT (0.01 elapsed), 0.68 MUT (0.94 elapsed), 0.48 GC (0.48 elapsed) :ghc make[2]: *** [Graphics/UI/GLUT/Window.o] Fehler 1 make[1]: *** [all] Fehler 1 make[1]: Leaving directory `/var/tmp/portage/ghc-5.05.20021109/work/stage3-build/libraries' make: *** [all] Fehler 1 Cheers, Ralf ___ Glasgow-haskell-bugs mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: Nightly build snapshots available
Enjoy... Will do ... I would appreciate a little note saying this snapshot is ok, or this one is horribly broken, or maybe this one is a milestone, if this is at all possible. But, thanks anyway, Ralf ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
glibc 2.3.1
Hi, some days ago I upgraded the GNU libc6 (also called glibc2) C library to version 2.3.1. It's only now that I notice that this wasn't a very good idea as it breaks GHC (version 5.04.1). basilisk Software/Haskell ghc --make Hello.hs ghc-5.04.1: chasing modules from: Hello.hs Compiling Main ( Hello.hs, ./Hello.o ) ghc: linking ... /usr/lib/ghc-5.04.1/libHSrts.a(RtsFlags.o)(.text+0xcf): In function `splitRtsFlags': : undefined reference to `__ctype_b' /usr/lib/ghc-5.04.1/libHSrts.a(RtsFlags.o)(.text+0xfb): In function `splitRtsFlags': : undefined reference to `__ctype_b' /usr/lib/ghc-5.04.1/libHSrts.a(RtsFlags.o)(.text+0x114): In function `splitRtsFlags': : undefined reference to `__ctype_b' collect2: ld returned 1 exit status I guess that the GNU library is broken, so this is not exactly a GHC bug report but more a word of warning. Cheers, Ralf ___ Glasgow-haskell-bugs mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Generating docs
What is the approved way of generating and installing docs? I tried (from source) ./configure ... make all make install make html make dvi make ps make install-docs The latter command fails with (as usual with a bit of German :-) --- ==fptools== make install-docs -wr; in /home/ralf/tmp/ghc-5.04.1/libraries/base t Haskell Core Libraries (base package) --no-implicit-prelude -p prologue.txt-h -o html Control/Arrow.raw-hs Control/Concurrent.raw-hs Control/Concurrent/Chan.raw-hs Control/Concurrent/MVar.raw-hs Control/Concurrent/QSem.raw-hs Control/Concurrent/QSemN.raw-hs Control/Concurrent/SampleVar.raw-hs Control/Exception.raw-hs Control/Monad.raw-hs Control/Monad/Cont.raw-hs Control/Monad/Error.raw-hs Control/Monad/Fix.raw-hs Control/Monad/Identity.raw-hs Control/Monad/List.raw-hs Control/Monad/Monoid.raw-hs Control/Monad/RWS.raw-hs Control/Monad/Reader.raw-hs Control/Monad/ST.raw-hs Control/Monad/ST/Lazy.raw-hs Control/Monad/ST/Strict.raw-hs Control/Monad/State.raw-hs Control/Monad/Trans.raw-hs Control/Monad/Writer.raw-hs Control/Parallel.raw-hs Data/Array.raw-hs Data/Array/Base.raw-hs Data/Array/Diff.raw-hs Data/Array/IArray.raw-hs Data/Array/IO.raw-hs Data/Array/MArray.raw-hs Data/Array/ST.raw-hs Data/Array/Storable.raw-hs Data/Array/Unboxed.raw-hs Data/Bits.raw-hs Data/Bool.raw-hs Data/Char.raw-hs Data/Complex.raw-hs Data/Dynamic.raw-hs Data/Either.raw-hs Data/FiniteMap.raw-hs Data/IORef.raw-hs Data/Int.raw-hs Data/Ix.raw-hs Data/List.raw-hs Data/Maybe.raw-hs Data/PackedString.raw-hs Data/Ratio.raw-hs Data/STRef.raw-hs Data/STRef/Lazy.raw-hs Data/STRef/Strict.raw-hs Data/Set.raw-hs Data/Tuple.raw-hs Data/Unique.raw-hs Data/Word.raw-hs Debug/QuickCheck.raw-hs Debug/QuickCheck/Batch.raw-hs Debug/QuickCheck/Poly.raw-hs Debug/QuickCheck/Utils.raw-hs Debug/Trace.raw-hs Foreign.raw-hs Foreign/C.raw-hs Foreign/C/Error.raw-hs Foreign/C/String.raw-hs Foreign/C/Types.raw-hs Foreign/C/TypesISO.raw-hs Foreign/ForeignPtr.raw-hs Foreign/Marshal/Alloc.raw-hs Foreign/Marshal/Array.raw-hs Foreign/Marshal/Error.raw-hs Foreign/Marshal/Utils.raw-hs Foreign/Ptr.raw-hs Foreign/StablePtr.raw-hs Foreign/Storable.raw-hs GHC/Arr.raw-hs GHC/Base.raw-hs GHC/Conc.raw-hs GHC/Enum.raw-hs GHC/Err.raw-hs GHC/Exception.raw-hs GHC/Exts.raw-hs GHC/Float.raw-hs GHC/Handle.raw-hs GHC/IO.raw-hs GHC/IOBase.raw-hs GHC/Int.raw-hs GHC/List.raw-hs GHC/Num.raw-hs GHC/Pack.raw-hs GHC/Posix.raw-hs GHC/PrimopWrappers.raw-hs GHC/Ptr.raw-hs GHC/Read.raw-hs GHC/Real.raw-hs GHC/ST.raw-hs GHC/STRef.raw-hs GHC/Show.raw-hs GHC/Stable.raw-hs GHC/Storable.raw-hs GHC/TopHandler.raw-hs GHC/Weak.raw-hs GHC/Word.raw-hs Numeric.raw-hs Prelude.raw-hs System/CPUTime.raw-hs System/Cmd.raw-hs System/Console/GetOpt.raw-hs System/Directory.raw-hs System/Environment.raw-hs System/Exit.raw-hs System/IO.raw-hs System/IO/Error.raw-hs System/IO/Unsafe.raw-hs System/Info.raw-hs System/Locale.raw-hs System/Mem.raw-hs System/Mem/StableName.raw-hs System/Mem/Weak.raw-hs System/Random.raw-hs System/Time.raw-hs Text/Html.raw-hs Text/Html/BlockTable.raw-hs Text/ParserCombinators/Parsec.raw-hs Text/ParserCombinators/Parsec/Char.raw-hs Text/ParserCombinators/Parsec/Combinator.raw-hs Text/ParserCombinators/Parsec/Error.raw-hs Text/ParserCombinators/Parsec/Expr.raw-hs Text/ParserCombinators/Parsec/Language.raw-hs Text/ParserCombinators/Parsec/Perm.raw-hs Text/ParserCombinators/Parsec/Pos.raw-hs Text/ParserCombinators/Parsec/Prim.raw-hs Text/ParserCombinators/Parsec/Token.raw-hs Text/ParserCombinators/ReadP.raw-hs Text/ParserCombinators/ReadPrec.raw-hs Text/PrettyPrint.raw-hs Text/PrettyPrint/HughesPJ.raw-hs Text/Read.raw-hs Text/Read/Lex.raw-hs Text/Regex.raw-hs Text/Regex/Posix.raw-hs Text/Show.raw-hs Text/Show/Functions.raw-hs \ --dump-interface=base.haddock \ /bin/sh: t: command not found make[2]: [html/index.html] Fehler 127 (ignoriert) /bin/install -c -m 644 -g users html/* /home/ralf/tmp/share/ghc-5.04.1/html/base /bin/install: Aufruf von stat für »html/*« nicht möglich: Datei oder Verzeichnis nicht gefunden make[2]: *** [install-docs] Fehler 1 make[1]: *** [install-docs] Fehler 1 make[1]: Verlassen des Verzeichnisses Verzeichnis »/home/ralf/tmp/ghc-5.04.1/libraries« make: *** [install-docs] Fehler 1 --- It seems that the call is a bit truncated. Cheers, Ralf ___ Glasgow-haskell-bugs mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: Generating docs
What is the approved way of generating and installing docs? I tried (from source) ./configure ... make all make install make html make dvi make ps make install-docs The latter command fails with (as usual with a bit of German :-) Do you have Haddock installed? Did the configure script detect it? Cheers, Simon No, of course not. Thanks. BTW, why did you separate Haddock from GHC? I love these vicious circles: to build GHC with docs you need Haddock, to build Haddock you need GHC ... Cheers, Ralf ___ Glasgow-haskell-bugs mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
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: DeepSeq
Beeing able to derive instances of DeepSeq would be nice too.
Here is an implementation using GHC's derivable type classes.
Cheers, Ralf
ghc -c -fglasgow-exts -fgenerics -package lang Eval.lhs
module Force
where
import Generics
class Force a where
force :: a - ()
force{|Unit|} a = a `seq` ()
force{|b :+: c|} a = case a of
Inl b - force b
Inr c - force c
force{|b :*: c|} a = case a of
b :*: c - force b `seq` force c
instance Force Char where
force a = a `seq` ()
instance Force Int where
force a = a `seq` ()
eval :: (Force a) = a - a
eval a= force a `s
___
Glasgow-haskell-users mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
GHC.Prim
Hi, ghci does not find GHC.Prim, but ghc does: :: A.lhs :: module A where import GHC.Prim a# i# j# = i# +# j# ralf/tmp ghc -c -fglasgow-exts A.lhs ralf/tmp ghci -fglasgow-exts A.lhs ___ ___ _ / _ \ /\ /\/ __(_) / /_\// /_/ / / | | GHC Interactive, version 5.03.20020410, for Haskell 98. / /_\\/ __ / /___| | http://www.haskell.org/ghc/ \/\/ /_/\/|_| Type :? for help. Loading package base ... linking ... done. Loading package haskell98 ... linking ... done. can't find module `GHC.Prim' Cheers, Ralf ___ Glasgow-haskell-bugs mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
qualified instance declarations
Hi, GHC (5.03.20020410) wrongly accepts the following: :: C.lhs :: module C where class A a where a :: a - Int :: X.lhs :: module X where import qualified C instance C.A Int where C.a = id Note that the class method is qualified on the LHS which is not legal H98. --- Incidentally, I also noticed that GHC and Hugs behave differently for the following variant of X.lhs. :: X.lhs :: module X where import qualified C instance C.A Int where a = const X.a a = 4 GHC happily accepts the file while Hugs complains that ERROR X.lhs:6 - Type error in instance member binding *** Term : a *** Type : a - Integer *** Does not match : Int - Int There seems to be a difference in defaulting. [Don't ask me which is the correct behaviour.] The problem disappears if I supply an explicit type signature for `a'. Cheers, Ralf ___ Glasgow-haskell-bugs mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Sorting and adaptive sorting
There seems to be a renewed interest in sorting and in adaptive sorting. A while ago (pre Haskell 98) I compiled a rather extensive library of sorting routines you may want to look at http://www.informatik.uni-bonn.de/~ralf/software.html#sort This includes different versions of mergesort, introspective sort (quicksort with a log n depth bound), heapsort etc. Cheers, Ralf ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
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
SuSE 8.0 packages
You can find GHC packages (version 5.03.20020410) for SuSE's latest distribution here: http://www.informatik.uni-bonn.de/~ralf/ghc-5.03.20020410-1.i386.rpm http://www.informatik.uni-bonn.de/~ralf/ghc-prof-5.03.20020410-1.i386.rpm http://www.informatik.uni-bonn.de/~ralf/ghc-5.03.20020410-1.src.rpm Have fun, Ralf ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
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
Re: preprocessing printf/regex strings (like ocaml)
I'm interested to know why a string translating preprocessor doesn't exist for haskell. It seems to me that it would alleviate printf and regex like problems in an convenient, elegant and type-safe manner. An example of this I came across recently was the ocaml printf statement: # Printf.printf roar;; roar- : unit = () # Printf.printf numbers %d %d 11 23;; numbers 11 23- : unit = () # Printf.printf a number %d word;; This expression has type string but is here used with type int You can see logically how this might work in haskell, compile time evaluation would translate the string into the appropriate native expressions before the statements type is evaluated. Incidentally, I've written a small functional pearl about implementing printf in Haskell, see http://www.informatik.uni-bonn.de/~ralf/publications.html#J11 Cheers, Ralf ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
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
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
Re: ANNOUNCE: GHC 5.03.20020410 snapshot released
Am Donnerstag, 18. April 2002 14:12 schrieb Simon Marlow: Ralf Hinze [EMAIL PROTECTED] writes: BTW, does this version support rank-n types? IIRC the previous snapshot did. So presumably this one does too? Yes, it does. Simon That's what I feared ;-). Ok, here is my first attempt at defining a rank-3 function (code attached). ghci responds --- ralf/Haskell ghci -v -fglasgow-exts Rank3.lhs ___ ___ _ / _ \ /\ /\/ __(_) / /_\// /_/ / / | | GHC Interactive, version 5.03.20020410, for Haskell 98. / /_\\/ __ / /___| | http://www.haskell.org/ghc/ \/\/ /_/\/|_| Type :? for help. Glasgow Haskell Compiler, Version 5.03.20020410, for Haskell 98, compiled by GHC version 5.03.20020410 ... *** Typechecker: Rank3.lhs:20: Illegal polymorphic type: forall b1 b2. (b1 - b2) - h1 f1 b1 - h2 f2 b2 In the type: forall h1 h2 a1 a2. (forall f1 f2. (forall c1 c2. (c1 - c2) - f1 c1 - f2 c2) - forall b1 b2. (b1 - b2) - h1 f1 b1 - h2 f2 b2) - (a1 - a2) - HFix h1 a1 - HFix h2 a2 While checking the type signature for `mapHFix' --- Do I have to hoist the forall quantifiers in bla - forall a . blub myself? At least, the code typechecks then. Cheers, Ralf ghci -v -fglasgow-exts Rank3.lhs data Fork a = ForkC a a mapFork :: forall a1 a2 . (a1 - a2) - (Fork a1 - Fork a2) mapFork mapA (ForkC a1 a2)= ForkC (mapA a1) (mapA a2) data SequF s a = EmptyF | ZeroF (s (Fork a)) | OneF a (s (Fork a)) newtype HFix h a = HIn (h (HFix h) a) type Sequ = HFix SequF mapSequF :: forall s1 s2 . (forall b1 b2 . (b1 - b2) - (s1 b1 - s2 b2)) - (forall a1 a2 . (a1 - a2) - (SequF s1 a1 - SequF s2 a2)) mapSequF mapS mapA EmptyF = EmptyF mapSequF mapS mapA (ZeroF as) = ZeroF (mapS (mapFork mapA) as) mapSequF mapS mapA (OneF a as)= OneF (mapA a) (mapS (mapFork mapA) as) mapHFix :: forall h1 h2 . (forall f1 f2 . (forall c1 c2 . (c1 - c2) - (f1 c1 - f2 c2)) - (forall b1 b2 . (b1 - b2) - (h1 f1 b1 - h2 f2 b2))) - (forall a1 a2 . (a1 - a2) - (HFix h1 a1 - HFix h2 a2)) mapHFix mapH mapA (HIn v) = HIn (mapH (mapHFix mapH) mapA v) mapSequ :: forall a1 a2 . (a1 - a2) - (Sequ a1 - Sequ a2) mapSequ = mapHFix mapSequF main= putStrLn hello world
Re: ANNOUNCE: GHC 5.03.20020410 snapshot released
BTW, does this version support rank-n types? ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
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: ANNOUNCE: GHC 5.03.20020410 snapshot released
Another snapshot along the 5.03 line, we expect this to be the last snapshot before 5.04. As before, there are NO GUARANTEES as to the stability of this release, but it has passed our three-stage bootstrap and all but one(!) of the 754 regressions tests passed. Documentation is also still lagging behind the new features. Hi, I tried ./configure --prefix=$HOME/Lang make all but the latter command fails with: mk/target.mk:45: mk/package.mk: Datei oder Verzeichnis nicht gefunden make: *** No rule to make target `mk/package.mk'. Stop. ls mk/ boilerplate.mk config.h config.mk opts.mk stamp-htarget.mk bootstrap.mkconfig.h.in config.mk.in paths.mk suffix.mk Am I missing something obvious? Cheers, Ralf ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
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 ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
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
Re: Functional Metapost revival
Dear Feri, You can find a version of Functional Metapost, which works with current (2001 February) Hugs, on the following page: http://afavant.elte.hu/~wferi/funcmp/ This version is able to produce all the illustrations in the enclosed Tutorial on my machine. Good luck, waiting for your comments: Feri. sorry for not being responsive. Currently, I don't have time to look into this. However, I put my current version of FMP on the web, which works both with Hugs (2001 February) and GHC. http://www.informatik.uni-bonn.de/~ralf/FuncMP-0.2.tar.gz Cheers, Ralf ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
SuSE 7.1 RPMs for ghc-5.02.1
You can find SuSE 7.1 RPMs for ghc-5.02.1 here http://www.informatik.uni-bonn.de/~ralf/ghc-5.02.1-1.i386.rpm http://www.informatik.uni-bonn.de/~ralf/ghc-prof-5.02.1-1.i386.rpm http://www.informatik.uni-bonn.de/~ralf/ghc-5.02.1-1.src.rpm Have fun, Ralf ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
undefined reference to `PrelGHC_Z2H_static_info'
Hi, I get a link error when I compile a program with -O2 Lexer2.o: In function `Lexer2_zdszdwlexCharLit_closure': Lexer2.o(.data+0x46c): undefined reference to `PrelGHC_Z2H_static_info' Lexer2.o: In function `Lexer2_zdszdwlexStrLit_closure': Lexer2.o(.data+0x484): undefined reference to `PrelGHC_Z2H_static_info' collect2: ld returned 1 exit status Everything works just fine if I use -O or no optimization. I can send you the bundle separately if you want me to. Cheers, Ralf ___ Glasgow-haskell-bugs mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
forall for all places
GHC 5.02 accepts forall types only at some sensible places:
this works
data CPS a = CPS { unCPS :: forall ans . (a - ans) - ans }
this doesn't work
newtype CPS a = CPS { unCPS :: forall ans . (a - ans) - ans }
this works
newtype CPS a = CPS (forall ans . (a - ans) - ans)
Needless to say that I prefer the second variant (which Hugs happily
accepts).
Cheers, Ralf
___
Glasgow-haskell-bugs mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
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/
Haskell Workshop 2001 http://www.cs.uu.nl/~ralf/hw2001.html
Registration Informationhttp://music.dsi.unifi.it/pli01
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
Re: No luck installing on SuSE 7.1
Dear William, using Manuel's SRPM I have built RPMs for SuSE 7.1. Would you like to serve as a beta-tester for these builds? I am not very confident whether the dependencies are ok. Generating the documentation for GHC was a mess; the SGML tools in the SuSE 7.1 distribution seem to be broken and I used the 7.0 tools (which are broken as well, but at least I was able to fix them). I placed the packages here http://www.informatik.uni-bonn.de/~ralf/ghc-5.00-2.src.rpm http://www.informatik.uni-bonn.de/~ralf/ghc-5.00-2.i386.rpm http://www.informatik.uni-bonn.de/~ralf/ghc-prof-5.00-2.i386 http://www.informatik.uni-bonn.de/~ralf/happy-1.9-1.i386.rpm Please let me know if you encounter any problems. BTW I have no idea why GHC from CVS does not work on your machine. Sorry. Cheers, Ralf ___ Glasgow-haskell-bugs mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
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
GHC from CVS
Dear all, after the failed attempts to install ghc 5.00 from the packages you provide, I downloaded ghc from the cvs repository. It compiles just fine except that ghci is not built: ghci ghc-5.00: not built for interactive use Do I have to specify this explicitly? Cheers, Ralf ___ Glasgow-haskell-bugs mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
GHC-5.00, first attempts
Dear all, here are the results from my first attempts to install ghc-5.00 on my linux machine: o Using the binary package: I was not able to install the documentation: make install-docs ./mkdirhier /home/ralf/Lang/share/ghc-5.00 cp -r html/* /home/ralf/Lang/share/ghc-5.00 chmod -R 644 /home/ralf/Lang/share/ghc-5.00 chmod: getting attributes of `/home/ralf/Lang/share/ghc-5.00/set': Keine Berechtigung make: *** [install-html] Error 1 `ghc' expects `libreadline.so.3' while I have `libreadline.so.4' installed on my machine. ghci /home/ralf/Lang/lib/ghc-5.00/ghc-5.00: error while loading shared libraries: libreadline.so.3: cannot open shared object file: No such file or directory locate readline.so /lib/libreadline.so.4 /lib/libreadline.so.4.1 /usr/lib/libreadline.so o Building from source: ===fptools== Finished making `boot' in cbits ... PWD = /home/ralf/Lang/ghc-5.00/ghc/lib/std ../../../ghc/utils/hsc2hs/hsc2hs-inplace Directory.hsc ../../../ghc/utils/hsc2hs/hsc2hs-inplace: /test/v-julsew/Nightly-HEAD/i386-unknown-linux/stage1/ghc/utils/hsc2hs/hsc2hs-bin: Datei oder Verzeichnis nicht gefunden make[3]: *** [Directory.hs] Error 127 make[2]: *** [boot] Error 1 make[1]: *** [boot] Error 1 make[1]: Leaving directory `/home/ralf/Lang/ghc-5.00/ghc' make: *** [all] Error 1 Any suggestions? Ralf ___ Glasgow-haskell-bugs mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
RE: Documentation
Yup, you have to explicitly ask for the documentation. Go to ghc/docs/set, and type 'make set'. The full documentation (combined Users' Guide and Library reference) will end up in set/ after a while. That does not work. make answers make: *** No rule to make target `set'. Any ideas? Do I have to take special actions when configuring? Ralf ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
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 "function" 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
Misleading error message
The following error message might be a bit misleading ;-) None of the type variable(s) in the constraint `C a' appears in the type `a - b' In the type signature for `op' Here is the source class C a where op :: (C a) = a - b which is not legal Haskell 98 (cf page 45: "the cx_i may not constrain u"). BTW Hugs 98 silently accepts the program. 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: `sort'
| If you want others, check out Ralf Hinze's pages at | |http://www.informatik.uni-bonn.de/~ralf/ Actually, http://www.informatik.uni-bonn.de/~ralf/Sort.tar.gz The library includes several adaptive sorting algorithms, an O(n log n) `quick sort' (aka introspective sort) ... Unfortunately, the library is currently in a state of flux. I will continue to work on it in April. Cheers, 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
| 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
