June 2007 - Haskell-Cafe

Construct all possible trees
by Andrew Coppin 14 Jun '07

14 Jun '07

I'm trying to construct a function all_trees :: [Int] -> [Tree] such that all_trees [1,2,3] will yield [ Leaf 1, Leaf 2, Leaf 3, Branch (Leaf 1) (Leaf 2), Branch (Leaf 1) (Leaf 3), Branch (Leaf 2) (Leaf 1), Branch (Leaf 2) (Leaf 3), Branch (Leaf 3) (Leaf 1), Branch (Leaf 3) (Leaf 2), Branch (Branch (Leaf 1) (Leaf 2)) (Leaf 3), Branch (Branch (Leaf 1) (Leaf 3)) (Leaf 1), Branch (Branch (Leaf 2) (Leaf 1)) (Leaf 3), Branch (Branch (Leaf 2) (Leaf 3)) (Leaf 1), Branch (Branch (Leaf 3) (Leaf 1)) (Leaf 2), Branch (Branch (Leaf 3) (Leaf 2)) (Leaf 1), Branch (Leaf 1) (Branch (Leaf 2) (Leaf 3)), Branch (Leaf 1) (Branch (Leaf 3) (Leaf 2)), Branch (Leaf 2) (Branch (Leaf 1) (Leaf 3)), Branch (Leaf 2) (Branch (Leaf 3) (Leaf 2)), Branch (Leaf 3) (Branch (Leaf 1) (Leaf 2)), Branch (Leaf 3) (Branch (Leaf 2) (Leaf 1)) ] So far I'm not doing too well. Here's what I've got: data Tree = Leaf Int | Branch Tree Tree pick :: [x] -> [(x,[x])] pick = pick_from [] pick_from :: [x] -> [x] -> [(x,[x])] pick_from ks [] = [] pick_from ks [x] = [] pick_from ks xs = (head xs, ks ++ tail xs) : pick_from (ks ++ [head xs]) (tail xs) setup :: [Int] -> [Tree] setup = map Leaf tree2 :: [Tree] -> [Tree] tree2 xs = do (x0,xs0) <- pick xs (x1,xs1) <- pick xs0 return (Branch x0 x1) all_trees ns = (setup ns) ++ (tree2 $ setup ns) Clearly I need another layer of recursion here. (The input list is of arbitrary length.) However, I need to somehow avoid creating duplicate subtrees... (BTW, I'm really impressed with how useful the list monad is for constructing tree2...)

6 14

TorDNSEL
by Tim Newsham 14 Jun '07

14 Jun '07

I wanted to point out: http://exitlist.torproject.org/ written in Haskell. I haven't seen any announcements or info on this list (apologies if someone else mentioned it already). For the record, I'm not affiliated with the project in any way. Tim Newsham http://www.thenewsh.com/~newsham/

2 2

Reading open data types
by Benja Fallenstein 13 Jun '07

13 Jun '07

Hi all, We've had a discussion on #haskell about how we can make a function that reads in serialized values of an open data type, such as class (Show a, Read a) => MyClass a where typeTag :: a -> String ... operations on the open data type... data Obj = forall a. MyClass a => Obj { unObj :: a } We would like to write a function like, oread :: String -> Obj The problem here is that unlike with 'read,' the calling context of 'oread' does not fix the implementation of Read that we want to use. The best we've been able to come up with was to build a table that maps type names to types: type TypeTable = Map String Obj oread :: TypeTable -> String -> Obj oread types s = Obj $ read repr `asTypeOf` unObj (types ! tag) where tag = takeWhile (/= ' ') s repr = drop 1 $ dropWhile (/= ' ') s instance Show Obj where show (Obj x) = typeTag x ++ " " ++ show x As far as we can see, we'll have to create this table manually, without support from the compiler. My suggestion would be to put the code constructing the table for each module at the top of that module, to keep it together with the exports and imports, like this: module Foo.Foo (export1, export2, fooFooTypes) where import Foo.Bar import Foo.Baz import Data.Map fooFooTypes = fooBarTypes `union` fooBazTypes `union` fromList [ ("Foo.Foo.Ty1", Obj (undefined :: Ty1)) , ("Foo.Foo.Ty2", Obj (undefined :: Ty2)) ] However, this is still kind of boring. Is there a better way? If not, would it be a good idea to have compiler support for building this kind of type table? Thanks, - Benja

4 6

Re: [Haskell] Who pays for *.haskell.org machines?
by Bulat Ziganshin 13 Jun '07

13 Jun '07

Hello Malcolm, Wednesday, June 13, 2007, 1:55:43 PM, you wrote: > In addition, we are in the process of setting up a separate server called > code.haskell.org thank you, it's all are great news. some questions: when you plan to make code.haskell.org available? is its funding will be reliable? for example, if we don't get money from Google in 2008 year? i hope that this server will be established as comfortable place for collective work, including wiki, bug tracker, darcs, so on, so on -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

6 5

Redefining Disjunction
by PR Stanley 13 Jun '07

13 Jun '07

Hi Can you think of a fourth way of redefining disjunct using pattern matching? vee :: Bool -> Bool -> Bool vee _ True = True vee True _ = True vee _ _ = False ve :: Bool -> Bool -> Bool ve True True = True ve True False = True ve False True = True ve False False = False v :: Bool -> Bool -> Bool v True b = True v b True = True v b False = b v False b = b Thanks Paul

4 3

Construct all possible trees
by Tom Pledger 13 Jun '07

13 Jun '07

*Andrew Coppin wrote: * | I'm trying to construct a function | | all_trees :: [Int] -> [Tree] | | such that all_trees [1,2,3] will yield : If you write a helper function that takes an N element list, and returns all 2^N ways of dividing those elements into 2 lists, e.g. splits "ab" --> [("ab",""),("b","a"),("a","b"),("","ab")] then you can use it both for dividing the initial list into kept and discarded elements, and for dividing a list between a left subtree and a right subtree. Regards, Tom

2 1

Re: [Haskell] ANNOUNCE: Harpy -- run-time code generation library
by Martin Grabmueller 13 Jun '07

13 Jun '07

[Moved to haskell-cafe] Daniel Mahler schrieb: > Given your reservation regarding LLVM, > you may be interested in vmgen, developed and used as a part of gforth. > It is also claimed that a JVM built with vmgen had performance comparable > to state of the art JITs. > If I remember the author of both gforth (including vmgen) and the > experimantal JVM, > is Anton Ertl. > Personally I have never used it, and do not know how good it is, > so I am not trying to push it. [...] > Anyway as I said, I do not know how much mileage you could get out of it, > but it seemed to be worth mentioning, given what you said about LLVM. Thanks for the pointer to vmgen. From a brief look at the docs and the source code, though, it seems that it supports the generation of threaded interpreters (which are efficient, but not as efficient as real native code) only, whereas we are interested in "real" code generation. Greetings, Martin

1 0

PhD student on Real-life datatype-generic programming
by Johan Jeuring 13 Jun '07

13 Jun '07

=================================================== Vacancy PhD student on Real-life datatype-generic programming Software Technology, Utrecht University, The Netherlands. =================================================== Within the Software Technology group of the Information and Computing Sciences department of Utrecht University there is a vacancy for a PhD student to work on Real-life datatype-generic programming. The position is funded by NWO, the Netherlands Organisation for Scientific Research. ------------------------------------------------------------------------ ----------------- Project summary: Datatype-generic programming has been around for more than 10 years now. We think a lot of progress has been made in the last decade. As an example, there are more than 10 proposals for generic-programming libraries or language extensions just for the lazy functional- programming language Haskell. Although generic programming has been applied in several applications, it lacks users for real-life projects. This is understandable. Developing a large application takes a couple of years, and choosing a particular approach to generic programming for such a project involves a risk. Few approaches that have been developed over the last decade are still supported, and there is a high risk that the chosen approach will not be supported anymore, or that it will change in a backwards-incompatible way in a couple of years time. We propose to create an environment that supports developing real- life applications using generic-programming techniques. We will focus on developing: - a library or a mixture of a library with a language extension for which we will guarantee continuing support. - an example of a real-life application fundamentally using generic- programming techniques. This application will serve as a showcase for generic-programming support for software development and evolution. - generic-programming design patterns. The usage of the generic- programming techniques in real-life projects will exhibit recurrent patterns, and will give valuable advice for and help with developing other applications using generic-programming techniques. Thus we will show how generic programming can be used to develop powerful tools in little time, and that the resulting tools are easy to maintain, adapt, and reuse. ------------------------------------------------------------------------ ----------------- Requirements: Master degree in Computer Science, or equivalent. Good knowledge of functional programming, and several advanced computer science techniques. Knowledge of Haskell, parsing, rewriting, strategies, generic programming, etc. will be useful. Terms of employment: the PhD student should start as soon as possible, but no later than January 1, 2008. The position is for four years (after one year there will be an evaluation), full-time. Gross salary starts with € 1956,-- per month in the first year and increases to € 2502,-- in the fourth year of employment. The salary is supplemented with a holiday bonus of 8% and an end-of-year bonus of 3%. In addition we offer: a pension scheme, partially paid parental leave, facilities for child care, flexible employment conditions in which you may trade salary for vacation days or vice versa. Conditions are based on the Collective Employment Agreement of the Dutch Universities. More information about the project can be found on http:// www.cs.uu.nl/~johanj/publications/nwo-ew2006.pdf More information about the Software Technology group on http:// www.cs.uu.nl/wiki/Center More information about the Information and Computing Sciences department on http://www.cs.uu.nl/ More information about this vacancy can be obtained from Johan Jeuring (johanj(a)cs.uu.nl, http://www.cs.uu.nl/~johanj/, +31 6 40010053). Send your application in pdf (or another non-proprietary format) to SciencePenO(a)uu.nl with a cc to johanj(a)cs.uu.nl. on or before July 31, 2007. We expect to arrange interviews in September. Mention vacancy nr 62712.

1 0

Mathematica
by Andrew Coppin 12 Jun '07

12 Jun '07

Hi folks. How difficult would it be to implement Mathematica in Haskell? I mean, I really like Mathematica, but it costs over £2,000. I can't really afford to pay that much for something that's only really a "toy". (It's not like a *need* it for anything, I just like playing with it.)

10 13

Just curios
by Andrew Coppin 12 Jun '07

12 Jun '07

OK, so this doesn't actually have anything to do with programming in Haskell, but... How in the name of God does a human being end up walking around with a name like "Haskell B. Curry"?

8 9