February 2005 - Haskell

Job Posting (Looking for a few good functional programmers)
by Yaron Minsky 03 Feb '05

03 Feb '05

Jane Street Capital (an affiliate of Henry Capital <http://henrycapital.com>) is a proprietary trading company located in Manhattan. The quantitative research department is responsible for analyzing, improving, and generating trading strategies. It's an open and informal environment (you can wear shorts and a t-shirt to the office), and the work is technically challenging, including systems work, machine learning, statistical analysis, parallel processing, and anything that crosses our path that looks useful. One unusual attraction of the job is that the large majority of our programming is done in OCaml. Pay is competitive, and we're a reasonably small company (around 85 employees), so advancement is pretty quick for someone who performs well. Here's what we're looking for: - Top-notch mathematical and analytic skills. We want people who can solve difficult technical problems, and think clearly and mathematically about all sorts of problems. - Strong programming skills. Pretty much all of our programming is in OCaml, so being a solid caml hacker is a big plus. But we're also interested in great programmers who we are convinced will be able to pick up OCaml quickly, so anyone with a high-level of proficiency with functional languages could be a good match. - Strong Unix/Linux skills --- We're looking for someone who knows their way around the standard unix tools, can write makefiles, shell scripts, etc. We use a beowulf cluster for compute-intensive jobs, so experience programming for and administering clusters is a big plus. If you're interested (or have any students you think might be a good match) and would be willing to relocate to New York, please send a cover-letter and resume to: yminsky(a)janestcapital.com

3 3

The Monad.Reader - Become an author for the Haskell eZine!
by Shae Matijs Erisson 03 Feb '05

03 Feb '05

There are plenty of academic papers about Haskell, and plenty of informative pages on the Haskell Wiki. But there's not much between the two extremes. The Monad.Reader aims to fit in there; more formal than a Wiki page, but less formal than a journal article. Want to write about a tool or application that deserves more attention? Have a cunning hack that makes coding more fun? Got that visionary idea people should know about? Write an article for The Monad.Reader! Contact Shae Erisson ( shae(a)ScannedInAvian.com ) to become an author, or talk to shapr on the #haskell irc channel on irc.freenode.net. Check the current roster - http://www.haskell.org/hawiki/TheMonadReader Publishing Format: * Input is LaTeX (or just plaintext and images). * Output is Web and PDF/PS. * Release once a month. * Each article in a darcs repo for easy collaboration between author and editor. License: *BSD-like, feel free to read it, teach it, hack it, copy it, improve it. The Monad.Reader: sequencing your input since 2005 -- Shae Matijs Erisson - http://www.ScannedInAvian.com/ - Sockmonster once said: You could switch out the unicycles for badgers, and the game would be the same.

1 0

Re: [Haskell] space behaviour of lazy recursive lists
by Axel Jantsch 03 Feb '05

03 Feb '05

Hi, Both variants of the strict zipWith solved the gibs problem I posed: gibs = 1 : 1 : f gibs (tail gibs) where f (x:xs) (y:ys) = z `seq` z : f xs ys where z = min (x + y) 10 by Simon MArlow and zipWith' f (x:xs) (y:ys) = let z = f x y in z `seq` (z : zipWith' f xs ys) zipWith' _ _ _ = [] by Adrian Hey However, they do not directly solve my problem in the bigger program which still has the same linearly growing memory requirement. The problem seems to be very, very hard to find. I suspect it is related to lazyness as in the gibs example, but I just cannot put my finger on the code that needs to be changed. Is there any good method to track down this kind of problem? (I tried all the ghc memory profiling techniques, that seemed promising to me.) Thanks to all that responded to my question! --Axel Axel Jantsch writes: > > Hi, > > How can I get constant space behaviour for lazy, recursive streams? > > Consider: > >> gibs = 1 : 1 : (zipWith f gibs (tail gibs)) >> where f x y = min (x + y) 10 > > This is derived from the fibs text book example, modified to bound the > memory requirement for each list element. > > Evaluating gibs should require constant amount of memory, since the > computed parts of the list are not needed any more and can be reclaimed. > > However, hugs says: > Main> nth 100 fibs > 10 > (2818 reductions, 3730 cells, 1 garbage collection) > Main> nth 200 fibs > 10 > (5618 reductions, 7430 cells, 1 garbage collection) > > which suggests linear space behaviour. Also, ghc shows the same behaviour > with a linearly growing stack size as shown by the profiler (+RTS -hc -xt) > and sooner or later the program runs out of memory with a stack overflow. > > It seems the entire list up to the last evaluated element is stored. Since > I want to use lazy streams to simulate process networks, I want to run the > simulation arbitrarily long without *ever* running out of memory. > > So my question is, how can I process recursive, lazy streams in constant > space? > > Or, in other words, how can I force the garbage collector to reclaim the > memory of the head of the list after I have processed it, since I will > never ever reference it again? > > With best regards > Axel Jantsch > > > --- > Phone: +46 8 790 4124, Email: axel(a)imit.kth.se, Web: www.imit.kth.se/~axel > _______________________________________________ > Haskell mailing list > Haskell(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell > > --- Phone: +46 8 790 4124, Email: axel(a)imit.kth.se, Web: www.imit.kth.se/~axel

2 1

Re: [Gph] [Fwd: Re: [Haskell] Implicit parallel functional programming]
by Phil Trinder 03 Feb '05

03 Feb '05

Satnam, > Does anyone know of any other work on implicitly > parallelizing functional programs for fine grain parallel execution? The skeletons community implicitly replace higher-order functions with parallel implementations: http://homepages.inf.ed.ac.uk/mic/Skeletons/ There's an excellent survey of parallel FP in Research Directions in Parallel Functional Programming, Hammond K. and Michaelson G. (Eds) Springer Verlag ISBN 1-85233-092-9 (2000). http://www-fp.dcs.st-and.ac.uk/pfpbook/ > there is interesting work with pH at MIT. Is anyone working on pH at the moment? Phil > ---------------------------- Original Message ---------------------------- > Subject: Re: [Haskell] Implicit parallel functional programming > From: mgross(a)dorsai.org > Date: Wed, January 19, 2005 4:36 am > To: "Satnam Singh" <satnams(a)microsoft.com> > Cc: Haskell(a)haskell.org > -------------------------------------------------------------------------- > > > > > > On Tue, 18 Jan 2005, Satnam Singh wrote: > >> I'm trying to find out about existing work on implicit parallel > functional programming. I see that the Glasgow Haskell compiler has a > parallel mode which can be used with PVM and there is interesting work > with pH at MIT. Does anyone know of any other work on implicitly > parallelizing functional programs for fine grain parallel execution? >> >> The emergence of multi-core processors makes me think that we should > look at implicit parallel functional programming in a new light. >> > At Brooklyn College, we are working on a version of Parallel Haskell that > does not require PVM. Instead, we use Internet protocols and the Mosix > patches to Linux. > > Murray Gross > Brooklyn College, CUNY > Metis Project > > > _______________________________________________ > Haskell mailing list > Haskell(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell > > > > _______________________________________________ > Gph mailing list > Gph(a)macs.hw.ac.uk > http://www.macs.hw.ac.uk/mailman/listinfo.cgi/gph > -------------------------------------------------- Phil Trinder School of Mathematical and Computer Sciences Heriot-Watt University Edinburgh, EH14 4AS E-mail: trinder(a)macs.hw.ac.uk Teleph: +44 (0)131 451 3435 Depart: +44 (0)131 451 3328 Fasmly: +44 (0)131 451 3327 Intrnt: http://www.macs.hw.ac.uk/~trinder

1 0

RE: [Haskell] Polymorphic types without type constructors?
by Simon Peyton-Jones 02 Feb '05

02 Feb '05

| It seems to me that the difference is: in the case of the second | definition of exp, the type variable in N can be instantiated to | a **monomorphic** type (the same with add and mul). | | exp2 = \m::N -> \n::N -> \f::(b -> b) -> \b::b -> | n [b] (m[b]) f b | | (where square brackets denote type application) | while in the first exp, n::N is instantiated to a **polymorphic** type | (another N): | | exp = \m::N -> \n::N -> \f::(b -> b) -> \b::b -> | (n[N] (mul m) one)[b] f b | | (SLPJ: note that N is a polymorphic type) You have it exactly right. The key word is "predicative". GHC has a predicative type system, that only allows you to instantiate a type variable with a monotype, not a polytype. An impredicative system (which is the one you want here) is more expressive, but it makes type inference very much more difficult. The algorithm is more difficult because type inference algorithms usually work with meta-type variables representing as-yet-unknown types; as the algorithm runs these meta-type variables are gradually substituted with their final type. But if this gradual substitution can involve polymorphic types, then type instantiation should have occurred earlier.... Try it yourself. Difficult is not impossible. If you are interested, look at MLF, a fantastic piece of work from INRIA (Remy & Le Botlan), that describes type inference for an impredicative, higher-rank type system. | I tried to add more type signatures to inform GHC of the fact | that n::N is to be instantiated to a polymorphic type. However | none of the attempts worked so far. Your intuition is good. Somehow, one might expect that if you told GHC *at the moment of instantiation* what to instantiate to, it ought to work, because there is no guessing involved. For example you ought to be able to say exp2 :: N -> N -> N exp2 n m = n {N} m Here, the {N} is a type argument to n. But I have not implemented this (yet). The main difficulty I encountered when thinking about is this. GHC uses prenex polytypes. If you write f :: Int -> (forall a. a->a) GHC behaves as if you'd written f :: forall a. Int -> a -> a That is, GHC's types never have a for-all to the right of an arrow. (You can read about this in "Practical type inference for higher rank types" on my home page.) Currently, this is a simple syntactic transformation on user-written types. But if you could instantiate a type variable with a polytype, then for-alls could occur to the right of an arrow as a result of the instantiation. My current plan is to throw out the prenex-polytype invariant, and find another way to deal with the problem that pushed me that way in the first place. Something like coloured type inference. I'm working on that with Dimitrios Vytiniotis and Stephanie Weirich. Anyway, thanks for an interesting example. Simon

2 1

Re: Polymorphic types without type constructors?
by oleg＠pobox.com 02 Feb '05

02 Feb '05

> I have been thinking about using Haskell (extended with > higher ranked polymorphism) to demonstrate to my colleagues > some ideas in second-order lambda calculus. It turned out, > however, I am puzzled by the type system myself. So I've > written to seek for help. :) > > I started with define Church numerals as > > > type N = forall a . (a -> a) -> a -> a > > (The syntax above works only for GHC. In Hugs I would have to write > type N a = (a -> a) -> a -> a > and replace every N below with (forall a. N a)) > I should have used newtype or data instead of a type synonym, > but I wanted it to look more like seond-order lambda calculus > so I tried to omit the constructor if possible. Let us consider a simpler example than the type N. > f1:: (forall a. a->a) -> b -> b > f1 g x = g x > -- *P1> f1 id True > -- True > > foo:: forall c notimportant. (c->c) -> notimportant > foo = undefined If we try > *P1> foo f1 we get an error > <interactive>:1: > Inferred type is less polymorphic than expected > Quantified type variable `a' escapes > Expected type: (a -> a) -> a -> a > Inferred type: (forall a1. a1 -> a1) -> b -> b > In the first argument of `foo', namely `f1' > In the definition of `it': it = foo f1 And indeed: the type of `foo' says that its argument must be a function from some type `c' to exactly the same type. The function f1 has the type (forall a. a->a) -> (forall b. b->b) The question then becomes: is (forall a. a->a) the same as (forall b. b->b) ? Not to Haskell. That would require a higher-order unification. However, not everything is lost. There is a way to convince GHC that the two quantified types are really the same. We just need a suitable envelope. Nominal equivalence does come handy sometimes. Here's the code > {-# OPTIONS -fglasgow-exts #-} > > module P1 where > > import Prelude hiding (succ) > > newtype N = N (forall a . (a -> a) -> a -> a) > un (N x) = x > > zero :: N > zero = N ( \f a -> a ) > > succ :: N -> N > succ n = N ( \f a -> f (un n f a) ) > > one:: N > one = succ zero > > add, mul :: N -> N -> N > add m n = N( \f a -> un m f (un n f a) ) > mul m n = N( \f a -> un m (un n f) a ) > > exp :: N -> N -> N > exp m n = un n (mul m) one > > exp2 :: N -> N -> N > exp2 m n = N (\f a -> un n (un m) f a) > > test1 = un (P1.exp two three) (+1) 0 > where two = succ one > three = succ two > > test2 = un (P1.exp2 two three) (+1) 0 > where two = succ one > three = succ two I must note that in this code, one may not replace N (...) with N $ ( ...). This is yet another case where ($) is not the same as an application with a lower precedence. The code has a redeeming feature: the data constructor N marks the places of explicit big-lambda introductions. The function 'un' marks the places of explicit big lambda eliminations (that is, type applications).

1 0

Re: Polymorphic types without type constructors?
by Shin-Cheng Mu 02 Feb '05

02 Feb '05

Hi, Shin-Cheng Mu wrote: > exp2 = \m::N -> \n::N -> \f::(b -> b) -> \b::b -> > n [b->b] (m[b]) f b Oops.. it should be exp2 = \m::N -> \n::N -> \f::(b -> b) -> \b::b -> n [b] (m[b]) f b sincerely, Shin-Cheng Mu

1 0

Polymorphic types without type constructors?
by Shin-Cheng Mu 02 Feb '05

02 Feb '05

Hi, I have been thinking about using Haskell (extended with higher ranked polymorphism) to demonstrate to my colleagues some ideas in second-order lambda calculus. It turned out, however, I am puzzled by the type system myself. So I've written to seek for help. :) I started with define Church numerals as > type N = forall a . (a -> a) -> a -> a (The syntax above works only for GHC. In Hugs I would have to write type N a = (a -> a) -> a -> a and replace every N below with (forall a. N a)) I should have used newtype or data instead of a type synonym, but I wanted it to look more like seond-order lambda calculus so I tried to omit the constructor if possible. I could define addition and multiplication smoothly. > zero :: N > zero = \f -> \a -> a > succ :: N -> N > succ n = \f -> \a -> f (n f a) > add, mul :: N -> N -> N > add m n = \f -> \a -> m f (n f a) > mul m n = \f -> \a -> m (n f) a But when it comes to exponential, GHCi complained about type being not polymorphic enough. > exp :: N -> N -> N > exp m n = n (mul m) one GHC said: Inferred type is less polymorphic than expected Quantified type variable `a' escapes Expected type: ((a -> a) -> a -> a) -> (a -> a) -> a -> a Inferred type: (forall a2. (a2 -> a2) -> a2 -> a2) -> (a1 -> a1) -> a1 -> a1 In the application `mul m' In the first argument of `n', namely `(mul m)' On the other hand, there is another definition of exp > exp2 :: N -> N -> N > exp2 m n = n m which would type check. It seems to me that the difference is: in the case of the second definition of exp, the type variable in N can be instantiated to a monomorphic type (the same with add and mul). exp2 = \m::N -> \n::N -> \f::(b -> b) -> \b::b -> n [b->b] (m[b]) f b (where square brackets denote type application) while in the first exp, n::N is instantiated to a polymorphic type (another N): exp = \m::N -> \n::N -> \f::(b -> b) -> \b::b -> (n[N] (mul m) one)[b] f b I tried to add more type signatures to inform GHC of the fact that n::N is to be instantiated to a polymorphic type. However none of the attempts worked so far. I then noticed that in the GHC User's Guide (Sec 7.4.9) it was written "There is one place you cannot put a forall: you cannot instantiate a type variable with a forall-type. So you cannot make a forall-type the argument of a type constructor." The examples followed are all about type constructors (for example [forall a. a->a], a list of for-all's, is illegal). But is this the reason why exp cannot be typed? If so, is there a reason for such a restriction? Thank you very much! sincerely, Shin-Cheng Mu

1 0

[OT] post-structuralist object oriented system
by PA 01 Feb '05

01 Feb '05

Not really a question, but rather for your entertainment: "Lua’s Story of O" http://alt.textdrive.com/lua/19/lua-story-of-o Cheers -- PA, Onnay Equitursay http://alt.textdrive.com/

1 0

Applying Functors
by Johan Glimming 01 Feb '05

01 Feb '05

Folks, I wonder if there is any particular reason for not having a class for object map of a functor (Functor-instances) in addition to the arrow map (fmap). Now you may say that this is just the constructor, but in my current example I have found it useful to have a general way of taking an object/value a into F a since the constructor can be arbitrary. I thought that I may need the return-operator in class Monad. I call it flift: class Lift f where flift :: a -> f a This works nicely for trivial datatypes like "data Unit a = Unit" and "data Id a = Id a": instance Lift Unit where flift a = Unit instance Lift Id where flift a = Id a My question is --- how would you define Lift for constructors such as data Sum a = Inl a|Inr a and so forth? Best Wishes, Johan Glimming

1 0