- Haskell-Cafe - Haskell.org

algebra proposals
by S.D.Mechveliani 16 May '01

16 May '01

It appears, there was a discussion on the library proposals, by D.Thurston, maybe, others. And people asked for my comments. My comments are as follows. ----------------------------------------------------------------- (1) It is misleading to call this part of the standard library `numeric': `numeric classes', `numeric Prelude', `Num', and so on. Matrices and polynomials match many of the corresponding instances but hardly can be named `numeric' objects. This is why BAL introduces the term Basic Algebra (items). (2) The order of considering problems matters. First we have to decide how to program algebra and then - whether (and how) to change the standard. The idea of the first stage forms the skeleton for the second. (3) As I see, we cannot decide how to program algebra in Haskell. Hence, it is better not to touch the standard - in order to save effort and e-mail noise. ----------------------------------------------------------------- Comments to (2) --------------- Anyone pretending to improve the standard has either to write any sensible algebraic Haskell application or to study attentively (with computing various examples) any existing one. A `sensible application' should show how to operate in parametric domains, not only in domains like (Integer, Bool). Example: polynomials in [x1..xn] with coefficients over a field (like rational numbers) quotiented by several equations. For example, the data r = Residue (x+y) (Ideal [x^2+3, y^3-2]) represents the mathematical expression squareRoot(-3) + cubicRoot(2) The basis bas = [x^2+3, y^3-2] for I = Ideal [x^2+3, y^3-2] can be computed as the first class data. And for many instances <Inst> (<Inst> may be Fractional, Field, ...) the domain (type?) of r matches or does not match <Inst> depending on the value of bas. Even if the application builds the domains only statically, when the compiler knows statically all the intended values of bas, Haskell would still meet difficulties. On dependent types ------------------ Maybe, Haskell has to move to dependent types. I am not sure, but probably, unsolvability does not matter. If the compiler fails to prove the correctness condition (on p) for a type T(p) within the given threshold d, the compiler reports "cannot prove ...". The user has to add annotations that help to prove this. Or to say "solve at run-time". Or to say "I postulate this condition on p, put the correctness on me". With kind regards, ----------------- Serge Mechveliani mechvel(a)botik.ru *** I am not in haskell-cafe list ***

1 0

RE: Functional programming in Python
by brk＠jenkon.com 15 May '01

15 May '01

> -----Original Message----- > From: Manuel M. T. Chakravarty [SMTP:chak@cse.unsw.edu.au] > Sent: Monday, May 14, 2001 10:46 PM > To: brk(a)jenkon.com > Cc: haskell-cafe(a)haskell.org > Subject: RE: Functional programming in Python > > brk(a)jenkon.com wrote, > > > > From: Manuel M. T. Chakravarty [SMTP:chak@cse.unsw.edu.au] > > Evidently this is wrong, but my intuition is that <- simply binds a > > name to a value, and that: > > No, that is not the case. It does more, it executes an I/O action. > [Bryn Keller] [snip] > The short answer is that Version 2 (the arrow) executes any > side effects encoded in `somefunc', whereas Version 1 (the > let binding) doesn't do that. Expressions given as an > argument to a function behave as if they were let bound, ie, > they don't execute any side effects. This explains why the > identity that you stated above does not hold. > > So, at the core is that Haskell insists on distinguishing > expressions that can have side effects from those that > cannot. This distinction makes the language a little bit > more complicated (eg, by enforcing us to distinguish between > `=' and `<-'), but it also has the benefit that both a > programmer and the compiler can immediately tell which > expressions do have side effects and which don't. For > example, this often makes it a lot easier to alter code > written by somebody else. It also makes it easier to > formally reason about code and it gives the compiler scope > for rather radical optimisations. > [Bryn Keller] Exactly the clarification I needed, thank you! [Bryn Keller] [snip] > > p.s. What data have your students' reactions given you about what is > > and is not difficult for beginners to grasp? > > They found it to be a difficult topic, but they found > "Unix/Shell scripts" even harder (and we did only simple > shell scripts). I actually made another interesting > observation (and keep in mind that for many that was their > first contact with programming). I had prepared for the > distinction between side effecting and non-side-effecting > expressions to be a hurdle in understanding I/O. What I > hand't taken into account was that the fact that they had > only worked in an interactive interpreter environment (as > opposed to, possibly compiled, standalone code) would pose > them a problem. The interactive interpreter had allowed > them to type in input and get results printed all way long, > so they didn't see why it should be necessary to complicate > a program with print statements. [Bryn Keller] Interesting! Thanks for your help, and for sharing your students' observations. I always knew shell scripting was harder than it ought to be. ;-) Bryn

1 0

RE: Functional programming in Python
by brk＠jenkon.com 15 May '01

15 May '01

> -----Original Message----- > From: Manuel M. T. Chakravarty [SMTP:chak@cse.unsw.edu.au] > Sent: Wednesday, May 09, 2001 12:57 AM > To: brk(a)jenkon.com > Cc: haskell-cafe(a)haskell.org > Subject: RE: Functional programming in Python > [Bryn Keller] [snip] > > > and I have to agree with Dr. Mertz - I find > > Haskell much more palatable than Lisp or Scheme. Many (most?) Python > > programmers also have experience in more typeful languages (typically at > > least C, since that's how one writes Python extension modules) so > perhaps > > that's not as surprising as it might seem. > > Ok, but there are worlds between C's type system and > Haskell's.[1] > [Bryn Keller] Absolutely! C's type system is not nearly so powerful or unobtrusive as Haskell's. > > Type inference (to my mind at least) fits the Python mindset very > > well. > > So, how about the following conjecture? Types essentially > only articulate properties about a program that a good > programmer would be aware of anyway and would strive to > reinforce in a well-structured program. Such a programmer > might not have many problems with a strongly typed language. [Bryn Keller] I would agree with this. > Now, to me, Python has this image of a well designed > scripting language attracting the kind of programmer who > strives for elegance and well-structured programs. Maybe > that is a reason. [Bryn Keller] This, too. :-) [Bryn Keller] [snip] > Absolutely. In fact, you have just pointed out one of the > gripes that I have with most Haskell texts and courses. The > shunning of I/O in textbooks is promoting the image of > Haskell as a purely academic exercise. Something which is > not necessary at all, I am teaching an introductory course > with Haskell myself and did I/O in Week 5 out of 14 (these > are students without any previous programming experience). > Moreover, IIRC Paul Hudak's book <http://haskell.org/soe/> > also introduces I/O early. > > In other words, I believe that this a problem with the > presentation of Haskell and not with Haskell itself. > > Cheers, > Manuel > > [1] You might wonder why I am pushing this point. It is > just because the type system seems to be a hurdle for > some people who try Haskell. I am curious to understand > why it is a problem for some and not for others. [Bryn Keller] Since my first mesage and your and Simon Peyton-Jones' response, I've taken a little more time to work with Haskell, re-read Tackling the Awkward squad, and browsed the source for Simon Marlow's web server, and it's starting to feel more comfortable now. In the paper and in the server souce, there is certainly a fair amount of IO work happening, and it all looks fairly natural and intuitive. Mostly I find when I try to write code following those examples (or so I think!), it turns out to be not so easy, and the real difficulty is that I can't even put my finger on why it's troublesome. I try many variations on a theme - some work, some fail, and often I can't see why. I should have kept all the versions of my program that failed for reasons I didn't understand, but unfortunately I didn't... The only concrete example of something that confuses me I can recall is the fact that this compiles: main = do allLines <- readLines; putStr $ unlines allLines where readLines = do eof <- isEOF if eof then return [] else do line <- getLine allLines <- readLines return (line : allLines) but this doesn't: main = do putStr $ unlines readLines where readLines = do eof <- isEOF if eof then return [] else do line <- getLine allLines <- readLines return (line : allLines) Evidently this is wrong, but my intuition is that <- simply binds a name to a value, and that: foo <- somefunc bar foo should be identical to: bar somefunc That was one difficulty. Another was trying to figure out what the $ sign was for. Finally I realized it was an alternative to parentheses, necessary due to the extremely high precedence of function application in Haskell. That high precedence is also disorienting, by the way. What's the rationale behind it? Struggling along, but starting to enjoy the aesthetics of Haskell, Bryn p.s. What data have your students' reactions given you about what is and is not difficult for beginners to grasp?

2 1

Re: Databases
by Justin: Member Since 1923 15 May '01

15 May '01

> > Is there an efficient way to make simple databases in Haskell? I mean >something like a dictionary, hash table or associative container of some kind. > > I'm aware that Haskell being pure functional means that those things >are not as easily implemented as they can be in other languages, in fact, >I've implemented a simple one myself, using a list of pairs (key,value) >(which means it's slow on lookup) and an optional monad to handle the >updates/lookups. > > I guess what I'm wondering is what has been done in this respect. There >is no such thing in the standard library, as far as I can see, and my >search through the web has turned up nothing. Chris Okasaki has developed a whole mess of purely function data structures. He has a book: http://www.cs.columbia.edu/~cdo/papers.html#cup98 Maybe this is what you're looking for? HTH -Justin

2 1

argument permutation and fundeps
by C T McBride 13 May '01

13 May '01

Hi This is a long message, containing a program which makes heavy use of type classes with functional dependencies, and a query about how the typechecker treats them. It might be a bit of an effort, but I'd be grateful for any comment and advice more experienced Haskellers can spare the time to give me. Er, this ain't no undergrad homework... I'm a dependently typed programmer and a bit of an old Lisphead. What's common to both is that it's fairly easy to write `program reconstruction operations', like the argument permutation function (of which flip is an instance), specified informally thus: Given a permutation p on [1..n] and an n-ary function f, permArg p f x_p(1) .. x_p(n) = f x_1 .. x_n It's easy in Lisp because you can just compute the relevant lambda-expression for permArg p f syntactically, then use it as a program: of course, there's no type system to make sure your p is really a perm and your f has enough arguments. To give permArg a precise type, we have to compute an n-ary permutation of the argument types for an n-ary function space. That is, we need a representation of permutations p from which to compute (1) the type of the permutation function (2) the permutation function itself This isn't that hard with dependent types, because we can use the same kinds of data and program as easily at the level of types as we can at the level of terms. I'm relatively new to Haskell: what attracted me is that recent extensions to the language have introduced a model of computation at the type level via multi-parameter classes with functional dependencies. Although type-level Haskell programming is separate from, different to, and not nearly as powerful as term-level Haskell programming, it's still possible to do some pretty interesting stuff: here's permArg as a Haskell program... Although we can't compute with types over a data encoding of permutations, we can use type classes to make `fake' datatypes one level up. Here's a class representing the natural numbers. Each type in the class has a single element, which we can use to tell the typechecker which instance of the class we mean. > class Nat n > data O = O > instance Nat O > data (Nat n) => S n = S n > instance (Nat n) => Nat (S n) Now, for each n in Nat, we need a class Fin n with exactly n instances. A choice of instance represents the position the first argument of an n-ary function gets shifted to. We can make Fin (S n) by embedding Fin n with one type constructor, FS, and chucking in a new type with another, FO. > class (Nat n) => Fin n x | x -> n > data (Nat n) => FO n = FO n > instance (Nat n) => Fin (S n) (FO n) > data (Nat n,Fin n x) => FS n x = FS n x > instance (Nat n,Fin n x) => Fin (S n) (FS n x) The class Factorial n contains n! types---enough to represent the permutations. It's computed in the traditional way, but this time the product is cartesian... > class (Nat n) => Factorial n p | p -> n > instance Factorial O () > instance (Factorial n p,Fin (S n) x) => Factorial (S n) (x,p) The operation InsertArg n x r s, where x is in Fin (S n), takes an n-ary function type s and inserts an extra argument type r at whichever of the (S n) positions is selected by x. The corresponding function, insertArg permutes a (S n)-ary function in r -> s by flipping until the first argument has been moved to the nominated position. FS codes `flip the argument further in and keep going'; FO codes `stop flipping'. > class (Nat n,Fin (S n) x) => > InsertArg n x r s t | x -> n, x r s -> t, x t -> r s where > insertArg :: x -> (r -> s) -> t > instance (Nat n) => InsertArg n (FO n) r s (r -> s) where > insertArg (FO _) f = f > instance (Nat n,Fin (S n) x,InsertArg n x r s t) => > InsertArg (S n) (FS (S n) x) r (a -> s) (a -> t) where > insertArg (FS _ x) f a = insertArg x (flip f a) PermArg simply works its way down the factorial, performing the InsertArg indicated at each step. permArg is correspondingly built with insertArg. > class (Nat n,Factorial n p) => > PermArg n p s t | p s -> t, p t -> s where > permArg :: p -> s -> t > instance PermArg O () t t where > permArg () t = t > instance (InsertArg n x r t u,PermArg n p s t) => > PermArg (S n) (x,p) (r -> s) u where > permArg (x,p) f = insertArg x (\r -> permArg p (f r)) This code is accepted by the Feb 2000 version of Hugs, of course with -98 selected. Let's look at some examples: the interesting thing is how the typechecker copes. Here's the instance of permArg which corresponds to flip Main> permArg (FS (S O) (FO O),(FO O,())) ERROR: Unresolved overloading *** Type : (InsertArg (S O) (FS (S O) (FO O)) a b c, InsertArg O (FO O) d e b, PermArg O () f e) => (a -> d -> f) -> c *** Expression : permArg (FS (S O) (FO O),(FO O,())) OK, I wasn't expecting that to work, because I didn't tell it the type of the function to permute: however, the machine did figure it out. Look at where it got stuck: I'd have hoped it would compute that e is f, and hence that b is d -> f, then possibly even that c is d -> a -> f. Isn't that what the functional dependencies say? On the other hand, if I tell it the answer, it's fine. Main> :t permArg (FS (S O) (FO O),(FO O,())) :: (a -> b -> c) -> b -> a -> c permArg (FS (S O) (FO O),(FO O,())) :: (a -> b -> c) -> b -> a -> c First, a nice little monomorphic function. > elemChar :: Char -> [Char] -> Bool > elemChar = elem There's no doubt about the type of the input, but this happens: Main> permArg (FS (S O) (FO O),(FO O,())) elemChar ERROR: Unresolved overloading *** Type : (InsertArg (S O) (FS (S O) (FO O)) Char a b, InsertArg O (FO O) [Char] c a, PermArg O () Bool c) => b *** Expression : permArg (FS (S O) (FO O),(FO O,())) elemChar What am I doing wrong? I hope my program says that c is Bool, and so on. Again, tell it the answer and it checks out: Main> :t (permArg (FS (S O) (FO O),(FO O,())) elemChar) :: [Char] -> Char -> Bool permArg (FS (S O) (FO O),(FO O,())) elemChar :: [Char] -> Char -> Bool Adding some arguments gives enough information about `the answer' to get rid of the explicit typing. Main> permArg (FS (S O) (FO O),(FO O,())) elemChar ['a','b','c'] 'b' True :: Bool It's the same story with arity 3... Main> :t permArg (FS (S (S O)) (FO (S O)),(FS (S O) (FO O),(FO O,()))) :: (a -> b -> c -> d) -> (c -> a -> b -> d) permArg (FS (S (S O)) (FO (S O)),(FS (S O) (FO O),(FO O,()))) :: (a -> b -> c -> d) -> c -> a -> b -> d Main> permArg (FS (S (S O)) (FO (S O)),(FS (S O) (FO O),(FO O,()))) foldl ERROR: Unresolved overloading *** Type : (InsertArg (S (S O)) (FS (S (S O)) (FO (S O))) (a -> b -> a) c d, InsertArg (S O) (FS (S O) (FO O)) a e c, InsertArg O (FO O) [b] f e, PermArg O () a f) => d *** Expression : permArg (FS (S (S O)) (FO (S O)),(FS (S O) (FO O),(FO O,()))) foldl Main> :t (permArg (FS (S (S O)) (FO (S O)),(FS (S O) (FO O),(FO O,()))) :: (a -> b -> c -> d) -> (c -> a -> b -> d)) foldl permArg (FS (S (S O)) (FO (S O)),(FS (S O) (FO O),(FO O,()))) foldl :: [a] -> (b -> a -> b) -> b -> b Main> permArg (FS (S (S O)) (FO (S O)),(FS (S O) (FO O),(FO O,()))) foldl [1,2,3] (+) 0 6 :: Integer So, am I failing to explain to Hugs why PermArg and InsertArg are programs, despite the explicit functional dependencies, or is the typechecker just not running them? It seems to be expanding PermArg's step case ok, but not executing the base case, leaving InsertArg blocked. Can anyone shed some light on the operational semantics of programming at the type level? Having, said all that, I'm really impressed that even this much is possible in Haskell. It's so nice to be able to write a type that says exactly what I mean. Cheers Conor

4 4

RE: Functional programming in Python
by brk＠jenkon.com 11 May '01

11 May '01

Hi Manuel, It's interesting to me to note the things that were interesting to you. :-) I'm the author of the Xoltar Toolkit (including functional.py) mentioned in those articles, and I have to agree with Dr. Mertz - I find Haskell much more palatable than Lisp or Scheme. Many (most?) Python programmers also have experience in more typeful languages (typically at least C, since that's how one writes Python extension modules) so perhaps that's not as surprising as it might seem. Type inference (to my mind at least) fits the Python mindset very well. I think most Python programmers would be glad to have strong typing, so long as they don't have to press more keys to get it. If you have to declare all your types up front, it just means more time spent changing type declarations as the design evolves, but if the compiler can just ensure your usage is consistent, that's hard to argue with. As for the difficulty with imperative constructs, I agree it's not even an issue for many (Dylan, ML, et. al.) languages, but for Haskell it still is, in my humble opinion. I found the task of writing a simple program that did a few simple imperative things inordinately difficult. I know about the 'do' construct, and I understand the difference between >> and >>=. I've read a book on Haskell, and implemented functional programming support for Python, but trying to use Haskell to write complete programs still ties my brain in knots. I see there are people writing complete, non-trivial programs in Haskell, but I don't see how. To be sure, I owe Haskell more of my time and I owe it to myself to overcome this difficulty, but I don't think it's only my difficulty. In the Haskell book I have, discussion of I/O is delayed until chapter 18, if memory serves. One thing that might really help Haskell become more popular is more documentation which presents I/O in chapter 2 or 3. Clearly the interesting part of a functional language is the beauty of stringing together all these functions into a single, elegant expression, but an introductory text would do well to focus on more immediate problems first. People on this list and others often say that the main body of the program is almost always imperative in style, but there's little demonstration of that fact - most examples are of a purely functional nature. Please understand I mean these comments in the most constructive sense. I have the highest respect for Haskell and the folks who work with it. Bryn > -----Original Message----- > From: Manuel M. T. Chakravarty [SMTP:chak@cse.unsw.edu.au] > Sent: Sunday, May 06, 2001 10:02 PM > To: haskell-cafe(a)haskell.org > Subject: Functional programming in Python > > Two quite interesting articles about FP in Python are over > at IBM developerWorks: > > http://www-106.ibm.com/developerworks/library/l-prog.html > http://www-106.ibm.com/developerworks/library/l-prog2.html > > Two IMHO interesting things to note are the following: > > * In Part 1, at the start, there is a bullet list of what > the author regards as FP "features". I found the > following interesting about this list: > > - There is no mention of the emphasis placed on strong > typing in many modern functional languages. > > - The author makes it sound as if FP can't handle > imperative features, whereas I would say that this is a > problem of the past and wasn't an issue in many FP > languages (Lisp, ML, ...) in the first place. > > The opinion of the author is not really suprising, but I > think, it indicates a problem in how FP presents itself > to the rest of the world. > > * In Part 2, the author writes at the end: > > I have found it much easier to get a grasp of functional > programming in the language Haskell than in Lisp/Scheme > (even though the latter is probably more widely used, if > only in Emacs). Other Python programmers might > similarly have an easier time without quite so many > parentheses and prefix (Polish) operators. > > I think, this is interesting, because both Lisp and Python > are dynammically typed. So, I would have expected the > strong type system to be more of a hurdle than Lisp's > syntax (or lack thereof). > > Cheers, > Manuel > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe

5 5

Re: sharing datatypes : best practice ?
by Jan Kort 11 May '01

11 May '01

"Taesch, Luc" wrote: > > do u isolate just the datatype, or a few related with, in a very small file (header like, i would say) > or some basic accessor function with it ? > > isnt it leading to massiv quantities of small files ? Asuming you have some typed AST with many mutually recursive datatypes, I would keep them in one big file. This should be fine if the datatypes are simple (no "deriving" Read and Show etc.). For an AST you don't want accessor functions: the datatypes are the interface. For some datatypes you want to hide the datatype and provide a function based interface, this should be in the same file as the datatype. Usually there is also some kind of asumed hierarchy in datatypes, e.g. Int < List < FiniteMap, to determine where functions operating on multiple datatypes should be placed, but that's the same in OO. Jan

1 0

Re: Macros[by implementor of toy compiler]
by Keith Wansbrough 08 May '01

08 May '01

> 2. Macros make the parsed grammar dynamic. Usually compiler has hard-coded > parser generated by LALR parser generator(like Happy or Yacc) compiled in. > Introducing each macro like you proposed would need(I think) generating > new parser(at least for the fragment of the grammar). Dylan has macros and a syntax more interesting than LISP's, so perhaps it would be worth looking at how they handle it. I forget now, but I don't think it was too difficult. I also considered some of the issues we're discussing in an unpublished paper that appears on my publications page, http://www.cl.cam.ac.uk/~kw217/research/papers.html#Wansbrough99:Macros (Section 8 looks briefly at Dylan-style macro facilities). --KW 8-)

1 0

Macros
by Alan Bawden 08 May '01

08 May '01

Date: Thu, 3 May 2001 18:09:01 -0500 (EST) From: Dan Knapp <dankna(a)brain.mics.net> > > (if (not (< x 3)) > > (assertion-failed '(< x 3))) > > This is a good example, which cannot be implemented in > Haskell. "Exception.assert" is built in to the ghc compiler, rather than > being defined within the language. On the other hand, the built in > function gives you the source file and line number rather than the literal > expression; the macro can't do the former. Yeah, it's a good example, but are there any other uses for such quoting? There are a few. But this isn't the -only- reason to still use macros. We could systematically go through all the macros I've written in the last few years, and for each one we could figure out what language feature would be needed in order to make that macro unnecessary. At the end of the process you would have a larger programming language, but I still wouldn't be convinced that we had covered all the cases. A macro facility is like a pair of vise-grips (if you don't know what those are, see http://www.technogulf.com/ht-vise.htm) You can do a lot of things with a pair of vise-grips, although usually there's a better tool for the job -- if you haven't got (say) a pipe-wrench, then a pair of vise-grips can substitute. Now the more tools you have in your tool box, the less often you will use your vise-grips. But no matter how bloated your tool box becomes, you will still want to include a pair of vise-grips for the unanticipated situation. I have one problem with my own analogy: If you find yourself using your vise-grips everyday for some task, you will probably soon go and purchase a more appropriate tool. But I think that in many circumstances macros do such a good job that I don't see the need to clutter up the language with the special-prupose features needed to replace them. Date: Fri, 04 May 2001 12:57:29 +0200 From: Jerzy Karczmarczuk <karczma(a)info.unicaen.fr> ... I think that they are less than popular nowadays because they are dangerous, badly structured, difficult to write "hygienically".... Indeed, you can screw up pretty badly with a pair of vise-grips! A friend of mine used to say that programmers should have to pass some kind of licensing test before they would be allowed to write Lisp/Scheme macros.

2 2

RE: Macros
by Simon Marlow 07 May '01

07 May '01

> Simon Marlow wrote: > > > > Well, simply extending the Haskell syntax to allow > > > > \ p11 .. p1n -> e1 > > .. > > pm1 .. pmn -> em > > > > (with appropriate layout) should be ok, but I haven't tried > it. Guarded > > right-hand-sides could be allowed too. > > Introducing layout after \ will break a lot of programs. For example, > consider the way >>= is often formatted: > > f >>= \x -> > g >>= \y -> > ... > > I guess that's why Marcin suggested using a new keyword. Ah yes, I forgot that lambda expressions are often used like that (actually, I think that this use of the syntax is horrible, but that's just MHO). Cheers, Simon

1 0