July 2002 - Haskell - Haskell.org

tuple component functions
by trb＠eastpac.com.au 03 Jan '03

03 Jan '03

S.D.Mechveliani writes: > As Haskell has the standard functions fst, snd to decompose (a,b), > maybe, it worths to provide also > tuple31, tuple31, tuple31, > ... > tuple51, tuple52, tuple53, tuple54, tuple55 > > for the tuples of n = 3,4,5 ? I've found some of these useful, except I named them differently: > fst3 :: (a,b,c) -> a > fst3 (x,_,_) = x > snd3 :: (a,b,c) -> b > snd3 (_,x,_) = x > thd3 :: (a,b,c) -> c > thd3 (_,_,x) = x .... never got around to quadruples etc. I also defined (some of these may be untested): > tripl :: a -> (a,a,a) > tripl x = (x,x,x) > curry3 :: ((a, b, c) -> d) -> a -> b -> c -> d > curry3 f x y z = f (x, y, z) > uncurry3 :: (a -> b -> c -> d) -> ((a, b, c) -> d) > uncurry3 f t = f (fst3 t) (snd3 t) (thd3 t) > applyTriple :: (a -> b, a -> c, a -> d) -> a -> (b,c,d) > applyTriple (f,g,h) x = (f x, g x, h x) > cross3 :: (a -> b, c -> d, e -> f) -> (a,c,e) -> (b,d,f) > cross3 (f,g,h) (x,y,z) = (f x, g y, h z) > mapTriple :: (a -> b) -> (a, a, a) -> (b, b, b) > mapTriple = cross3 . tripl > applyFst3 :: (a -> b) -> (a, c, d) -> (b, c, d) > applyFst3 f = applyTriple (f . fst3, snd3, thd3) > applySnd3 :: (a -> b) -> (c, a, d) -> (c, b, d) > applySnd3 f = applyTriple (fst3, f . snd3, thd3) > applyThd3 :: (a -> b) -> (c, d, a) -> (c, d, b) > applyThd3 f = applyTriple (fst3, snd3, f . thd3) > applyArgs3 :: (a -> b) -> (c -> d) -> (e -> f) -> (b -> d -> f -> g) -> (a -> c -> e -> g) > applyArgs3 af1 af2 af3 f = \x y z -> f (af1 x) (af2 y) (af3 z) > rotl :: (a -> b -> c -> d) -> (b -> c -> a -> d) > rotl f y z x = f x y z > rotr :: (a -> b -> c -> d) -> (c -> a -> b -> d) > rotr f z x y = f x y z > rotl4 :: (a -> b -> c -> d -> e) -> (b -> c -> d -> a -> e) > rotl4 f y z t x = f x y z t > rotr4 :: (a -> b -> c -> d -> e) -> (d -> a -> b -> c -> e) > rotr4 f t x y z = f x y z t Some more combinators (only for pairs so far): > twin :: a -> (a,a) > twin x = (x,x) > swap :: (a,b) -> (b,a) > swap (x,y) = (y,x) -- apply a pair of functions to one argument > applyPair :: (a -> b, a -> c) -> a -> (b, c) > applyPair (f, g) x = (f x, g x) -- apply a pair of functions to a pair > cross :: (a -> b, c -> d) -> (a, c) -> (b, d) > cross (f, g) = applyPair (f . fst, g . snd) -- compose a pair of functions onto one function > dotPair :: (a -> b, a -> c) -> (d -> a) -> (d -> b, d -> c) > dotPair (f, g) h = (f . h, g . h) -- compose a pair of functions onto a pair of functions > dotCross :: (a -> b, c -> d) -> (e -> a, f -> c) -> (e -> b, f -> d) > dotCross (f, g) (h, i) = (f . h, g . i) > mapPair :: (a -> b) -> (a, a) -> (b, b) > mapPair = cross . twin > applyFst :: (a -> b) -> (a, c) -> (b, c) > applyFst f = applyPair (f . fst, snd) > applySnd :: (a -> b) -> (c, a) -> (c, b) > applySnd f = applyPair (fst, f . snd) > applyArgs :: (a -> b) -> (c -> d) -> (b -> d -> e) -> (a -> c -> e) > applyArgs af1 af2 f = \x y -> f (af1 x) (af2 y) > betweenFst :: (a -> b -> c) -> (a, d) -> (b, e) -> c > betweenFst = applyArgs fst fst > betweenSnd :: (a -> b -> c) -> (d, a) -> (e, b) -> c > betweenSnd = applyArgs snd snd I find these combinators useful, and probably other people have their own versions - it would be nice to get them standardised, so we all speak the same language. By standardised, I mean a prominent version that will be adopted by users, not necessarily a committee process. Tim

3 2

ICFP programming contest
by trb＠eastpac.com.au 03 Jan '03

03 Jan '03

Michael Hobbs writes: > Just took a look at the results for the ICFP contest. Am I correct in > assuming that "LA" stands for Lennart Augustsson and that "Si^3" stands > for Simon Marlow, Simon Peyton-Jones, Sigbjorn Finne? Is there a URL for the results ? Tim

2 1

slightly ot: data structure question
by Hal Daume III 02 Aug '02

02 Aug '02

Not really Haskell-specific, but... I need a data structure which is a map from Ints to Doubles; the distribution of the Ints is in the range say 0-20000 and a map will contain somewhere around 100-200 elements. I need to be able to query *very* quickly, insert *quite* quickly, and iterate through the elements very quickly. I'm thinking hash tables, but I'm not sure. Does anyone have any thoughts on this? - Hal -- Hal Daume III "Computer science is no more about computers | hdaume(a)isi.edu than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume

2 1

monads, modules, sandboxes
by Daniel Crealer 01 Aug '02

01 Aug '02

Warning: pseudo-caml below since I don't know Haskell too well. But in trying to learn I came across interesting concept of monad, and that is what inspired the following idea. I would just like to know if anyone thinks it's interesting and if someone has already developed it. Inspired by monads, I had the following idea for controlled sandboxing of an application. I'll give you a very concrete scenario, but maybe it isn't the most interesting use of idea. I download a program off the Internet that claims to do some interesting transformation on my data. But I don't trust the application not to send my secret data back to the web site. I could achieve this by running the program in a sandbox that doesn't allow it to send data over the Internet. But maybe the program has legitimate reasons to send data, e.g., the company charges based on how much data I transform, so the program wants to periodically send messages to the web site saying it performed some units of work. The idea is just that if my data has type t, instead of a program of type t -> t, the website provides a program of type m -> m written in a monadic style. Actually m = t, and the bind operation (>>=) is trivial. But it is run in the sandbox. Here is pseudo-code, where MYDATA is thought of as a well-known signature of a well-known standard, like JPEG or something, with standard implementation MyData (though I could change MyData as long as I think my changes won't break the code I got off the web site) and DataTransformer is the untrusted code from the web site. In some applications, probably you could get away with just bind and return, but for the example I give here, the untrusted code needs a way to find out if the data is done being transformed. I implement that by providing an is_done function, but note that this could be a security hole. A safer way might be to have really_do_100_steps throw an exception when it finishes that would be caught by bind. module MyData = struct type t = ... type m = t let (>>=) mm f = try run_in_sandbox (fun _ -> f mm) with _ -> failwith "gotcha" let return x = x (* functions that only run in the sandbox *) ... things that take t's ... (* functions that can run outside the sandbox *) let is_done = ... ... other things that take m's ... end module type MYDATA = sig type t = ... type m val (>>=) : m -> (t -> m) -> m val return : t -> m is_done : m -> bool ... other stuff ... end module DataTransformer = struct let really_do_100_steps x = ... let do_100_steps x = x >>= (function y -> return (really_do_100_steps y)) let rec doit x = bill_customer_for_100_steps (); let x' = do_100_steps x in if is_done x' then x' else doit x' end _________________________________________________________________ Join the worlds largest e-mail service with MSN Hotmail. http://www.hotmail.com

3 2

good advanced fp (haskell) book
by Hal Daume III 01 Aug '02

01 Aug '02

Hi all, I'm looking to purchase one (perhaps two) books for my collection. I'm looking for two things in particular: - good algorithmic reference - good explanation of the meat of haskell (advanced stuff) I don't care about introductory stuff; I've written tens of thousands of lines of Haskell code and don't want to waste my time reading what a tuple is. I was looking at the "Algorithms: A Purely Functional Approach" online which, based on the contents, seems to satisfy well my first desire, but I fear it doesn't get advanced quickly enough and am left with only a little on advanced topics. All the other books I looked at on the bookshelf seemed too introductory. I'm not afraid of math (it was my undergraduate degree) and rather enjoy theorems, but I'm also insanely practical and am interested in a book which has a large section on *efficiency*. I fear what I'm looking for doesn't exist, and in the absense of a book, perhaps people could point me to good extended (perhaps journal?) papers -- though papers tend to largely ignore the efficiency stuff and serve as very poor references. Thanks! - Hal -- Hal Daume III "Computer science is no more about computers | hdaume(a)isi.edu than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume

3 2

Correction
by Carl McTague 31 Jul '02

31 Jul '02

I'm sorry, there was a subtle error in the definition of the function finAuDeterminize in my posting, which caused genuine performance trouble! Replace sort by (sort.nub). That is: finAuDeterminize :: (Ord l) => FinAu l -> FinAu [l] finAuDeterminize startStates = [f startStates] where f :: (Ord l) => [FaState l] -> FaState [l] f states = FaState label' acceptQ' trans' where label' = (sort.nub) (map label states) acceptQ' = or (map acceptQ states) trans' = map (singleton.f.concat) (transpose (map trans states)) singleton a = [a] Carl

1 0

Efficiency of list indices in definitions
by Carl McTague 31 Jul '02

31 Jul '02

Hi, I'm experimenting with various implementations of finite automata. I think the following is interesting, but gives rise to a question, which might actually be silly. (Forgive me if it is.) First, I can define a state as a recursive data type: data FaState l = FaState {label :: l, acceptQ :: Bool, trans :: [[FaState l]]} where l is the type of an arbitrary label. (This will become important a bit later on.) The trans is the adjacency list for state automaton: trans!!i is a list of all states reachable via the symbol i from the current state. (I use a list rather than an array because I typically work with binary alphabets, so the use of Arrays doesn't seem justified.) I make trans!!i a list so that I can represent nondeterminism. Then a finite automaton is merely a list of starting FaStates: type FinAu l = [FaState l] So, for example, an automaton equivalent to the regular expression 0*(0(0+1)*)* could be defined as: dom18 :: FinAu Int dom18 = [one,two] where one = FaState 1 True [[two],[]] two = FaState 2 True [[one],[one]] So, with this machinery in place we can define most of the classical constructions quite easily. For example, to check whether a given string is accepted by an automaton: finAuAcceptStringQ :: FinAu l -> [Int] -> Bool finAuAcceptStringQ startStates string = or [faStateAcceptStringQ s string | s <- startStates] where faStateAcceptStringQ (FaState _ acceptQ _) [] = acceptQ faStateAcceptStringQ (FaState _ _ trans) (a:as) | null followerStates = False | otherwise = or [ faStateAcceptStringQ s as | s <- followerStates ] where followerStates = if a > (length trans) - 1 then [] else trans!!a and the classical nfa-to-dfa power-set (determinization) construction may be implemented quite nicely with: finAuDeterminize :: (Ord l) => FinAu l -> FinAu [l] finAuDeterminize startStates = [f startStates] where f :: (Ord l) => [FaState l] -> FaState [l] f states = FaState label' acceptQ' trans' where label' = sort (map label states) acceptQ' = or (map acceptQ states) trans' = map (singleton.f.concat) (transpose (map trans states)) singleton a = [a] Now, we get to the heart of my question. This definition is quite lovely, recursive and lazy, but it doesn't actually capture the recurrent structure of the resulting automata. That is, if we were to compute: finAuAcceptStringQ (finAuDeterminize dom18) somestring then finAuDeterminize would keep spinning out, generating more and more states, which would actually be equivalent (and, have identical state labels). So an idea is that we can assume the state labels induce an equivalence relation on our states and define something like: finAuConsolidate :: (Eq l) => FinAu l -> FinAu l finAuConsolidate startStates = [ newStates!!i | l <- map label startStates, i <- elemIndices l (map fst assocs) ] where assocs = finAuStateLabelAssoc startStates newStates = map (f.snd) assocs f oldState@(FaState l acceptQ trans) = FaState l acceptQ (map (map (g.label)) trans) g label = case elemIndex label (map fst assocs) of Just i -> newStates!!i Nothing -> error "odd error in finAuConsolidate" provided we have defined: finAuStateLabelAssoc :: (Eq l) => FinAu l -> [(l,FaState l)] finAuStateLabelAssoc startStates = foldl f [] startStates where f knownStatesAssoc state@(FaState label _ trans) | isJust (lookup label knownStatesAssoc) = knownStatesAssoc | otherwise = foldl f ((label,state):knownStatesAssoc) followers where followers = concat trans So this is the heart of my question: is this the best way to proceed? Will the list lookups (!!) of finAuConsolidate be used only once in the construction or will they be perpetually used in something like: finAuAcceptStringQ ((finAuConsolidate.finAuDeterminize) dom18) somestring? That is, how much of a difference would it make if I were to use an Array instead? Thanks, Carl

1 0

edison question
by paul＠theV.net 31 Jul '02

31 Jul '02

I am quite confused with the collection package provided by the edison library. Attached is a sample program, what I wanted to do is to maintain a sorted of Pair of id and time (sorted by time). The error I got is: ghc -package data -package lang test.hs test.hs:17: No instance for `Collection.OrdColl c Pair' arising from use of `Collection.minElem' at test.hs:17 in a pattern binding: Collection.minElem sorted Actually I don't really understand what a class like "OrdColl c a" really means and how to use them. Please help! Regards, .paul.

4 4

ANNOUNCE: HOpenGL 1.03 released
by Sven Panne 30 Jul '02

30 Jul '02

HOpenGL, a Haskell binding for OpenGL and GLUT version 1.03 I am pleased to announce the fourteenth release of the Haskell binding for GL 1.2.1 / GLU 1.3 / GLUT 3.7beta. It offers easy access to *the* industrial strength 3D graphics API and a GUI toolkit. More details about HOpenGL can be found at http://haskell.org/HOpenGL It is yet another compatibility release, which fixes a few bugs in the configuration process and makes installation a bit more flexible. If you are happy with the previous version, you don't need this release, as there are no new features. What's new: * Fixed GLUT version test, so GLUT API version 4 features like game mode and key-up callbacks are correctly detected. * The automatic test for -split-objs works again. * Added support for installing HOpenGL in user-specified locations. * The values of CPPFLAGS and LDFLAGS during configuration are remembered. * The paths to build tools can contain spaces. * The test for GLX has been improved. * Added workaround for buggy SUN OpenGL header. * Renamed --with-Mesa and --with-efence configure options to --enable-Mesa and --enable-efence. As always, feedback and/or patches are highly welcome. Have fun! Sven

1 0

Haskell 98 report
by Simon Peyton-Jones 30 Jul '02

30 Jul '02

Folks I'm happy to say that the Haskell 98 Report (both language and libraries) is going to be published as a book! It'll be a (very) special issue of the Journal of Functional programming (Jan 2003), but will be available separately through bookshops as a book published by Cambridge University Press. I have had essentially no bug reports since the June release, which is great. (One or two typos but that is all.) I'll have to deliver source text to CUP in Sept/Oct; until then the gate is still open to fix actual errors, but the time has now passed for "wouldn't it be nice if..." stuff. The online version will continue to be available, of course, but I expect that you will all want to have the book on your shelves too. My paper copy is now well-thumbed. happy days, Simon

1 0