November 2006 - Haskell-Cafe

why are implicit types different?
by S. Alexander Jacobson 21 Nov '06

21 Nov '06

Why do g and g' have different types? g x y = let ?f = \x-> x in ?f x ++ (show (?f y)) g' x y = let f = \x-> x in f x ++ (show (f y)) Is there a way I can use implicit types and let g be as general as g'? -Alex- ______________________________________________________________ S. Alexander Jacobson tel:917-770-6565 http://alexjacobson.com

1 0

Friday Afternoon Play: The Burrows Wheeler Transformation
by Jón Fairbairn 21 Nov '06

21 Nov '06

So, it's Friday afternoon (well, here anyway), and presumably everyone is thinking of leaving for the weekend. Is anyone interested in playing a little game? I'm going to make the first move, and then just wait and see if anyone makes the next. I'm certainly not promising to make any further moves myself, but I'm not promising I won't, either. Below you'll see a naïve implementation of the Burrows Wheeler transformation and its inverse. That's my move. (And don't complain too much about style and such -- I'm half asleep.) Further moves are made by transforming the programme so that it becomes more efficient. The first target is not raw speed, but to adjust it until the computational complexity gets to be what it should be. I'm hoping for elegant moves here. After that, folk might start replacing the lists with more efficient datastructures and so on, but still /elegantly/. The object of the game isn't ultimate speed -- I've no particular wish to see a Haskell version that's as fast as a good C version, especially not if it ends up /looking/ like a C version. Really the objective is to think about Haskell programming -- and probably come up with some observations such as "there really ought to be a class of indexable structures, so that we don't have to change (!!) to (!) all over the place". And to have fun, anyhow... * * * Demonstration of the principle of the Burrows Wheeler transform. The implementations are simplistic (and have worse complexity than is possible). > module Burrows_Wheeler_Transform where > import List This is surely the wrong module to have to find (><) from: > import Data.Graph.Inductive.Query.Monad((><)) The forward transformation. Input a list, output the transformed list and possibly an int (Nothing if there were no elements in the input -- perhaps the result type should be Maybe (NonEmptyList t,Int)) > slow_bwt:: Ord t => [t] -> ([t], Maybe Int) This version works by computing a list of all the rotations of the input and sorting it. The transformation is then the last element of each line of the sorted rotations. Tag the data with an index so that it's possible to find where the original form of the unput ends up after sorting. This is essentially the specification of the transform coded up directly. > slow_bwt l > = (map fst tagged_bwt, index_of_original) > where tagged_bwt = map (last><id) > $ sort > $ rotations l`zip`[0..] > index_of_original = findIndex ((==0).snd) tagged_bwt that looks like worst case n²×log n to me (where n is the length of the string): if every element is the same, the n×log n comparisons the sort does will each look at every element, and that's really more than is necessary. The inverse transform. We should have that @ slow_inv_bwt . slow_bwt == id @ Observe that sorting the input gives the first column of the sorted rotations (and the input is the last). So after one sort we have X ... c Y ... b Z ... a . . . . . . . . . Since they are rotations, rotating each row of this gives pairs that belong to the original list: cX ... by ... aZ ... . . . . . . sorting these gives us the first two columns of the sorted rotations, and again we already know the last column, which can be rotated into the first and so on. > slow_inv_bwt ([],_) = [] > slow_inv_bwt (l,Just index_of_original) > = iterate catsort (replicate len []) After (length input) iterations we have the original sorted rotations, > !! len and we have the index of where the untransformed string is, so we can just pick it back out. > !! index_of_original > where catsort s = sort $ map (uncurry (:)) $ l `zip`s > len = length l This version does rather fewer sorts: > mark2_inv_bwt ([],_) = [] > mark2_inv_bwt (l,Just n) > = (transpose $ take (length l) $ iterate (permuteWith perm) l)!!(perm!!n) > where perm = map snd $ sort $ l `zip` [0..] Should I simply have left it out and hoped that it would turn up after a few moves? I'm not going to explain it, anyway. > rotations l = init $ zipWith (++) (tails l) (inits l) > permuteWith ns l = map (l!!) ns -- Jón Fairbairn Jon.Fairbairn(a)cl.cam.ac.uk

6 6

Newbie Haskell optimization question
by Slavomir Kaslev 21 Nov '06

21 Nov '06

Hello, I am new to Haskell and I am having fun with it writing L-system generator. I was very pleased with concise syntax. It's an order of magnitude better than any C++, Lisp, etc program I've ever written or read. Doing algorithmic optimizations on my generator I ended up with 4 different versions (you can see the other 3 in the file attached). The most optimal of them is: import qualified Data.Map type LSystemElement = (Char, [Int]) type LSystem = [LSystemElement] type LSystemRules = Data.Map.Map Char (LSystemElement -> LSystem) generate'' :: LSystemRules -> LSystem -> Int -> LSystem generate'' rules axiom steps = concatMap (iterate f axiom !!) (ind !! steps) where ind = [0] : [g x | x <- ind] where g [] = [] g [x] = [x, x + 1] g xs = xs ++ g (drop (length xs `div` 2) xs) f = concatMap $ \elem -> Data.Map.findWithDefault (\x -> [x]) (fst elem) rules elem -- Tests a (_, [x, y]) | y <= 2 = [('A', [x + 2, y + 2])] | otherwise = [('B', [2]), ('A', [x - 1, y - 1])] b (_, [x]) | x <= 2 = [('C', [])] | otherwise = [('B', [x - 1])] rules = Data.Map.fromList [('A', a), ('B', b)] axiom = [('A', [2, 2])] Now I am thinking of doing some language level optimizations. Can you give me any (random) directions? Any style recommendations are welcome as well. Cheers. -- Slavomir Kaslev

3 2

Re: topEq for types
by oleg＠pobox.com 21 Nov '06

21 Nov '06

Nicolas Frisby described the problem and the solution of the type equality comparison that takes into account the top-most type constructor only. Thus `Maybe Bool' should be considered equal to `Maybe Char' because both types have the same top constructor Maybe. The following complete code shows another solution. The code includes several tests, test1 through test6, along with the expected answers. {-# OPTIONS -fglasgow-exts #-} {-# OPTIONS -fallow-undecidable-instances #-} {-# OPTIONS -fallow-overlapping-instances #-} -- type equality for the top-level type constructor -- That is, decide two types to be equal if the top-most type constructor -- matches. Thus `Maybe Bool' should be considered equal to `Maybe Char' module TEQ where -- Our approach is simple. Given a type, we normalize it: -- replace all arguments of the type constructor with unit. -- After that, we use the regular HList's TypeEq. class Normalize t r | t -> r instance TypeCast (c ()) r => Normalize (c x) r instance TypeCast (c () ()) r => Normalize (c x y) r instance TypeCast (c () () ()) r => Normalize (c x y z) r -- add instances for type constructors of higher arities instance TypeCast y x => Normalize x y top_eq :: (Normalize a a', Normalize b b', TypeEq a' b' r) => a -> b -> r top_eq = undefined test1 = top_eq (undefined::Int) (undefined::Char) -- :t test1 -- test1 :: HFalse test2 = top_eq (undefined::Bool) (undefined::Bool) -- test2 :: HTrue test3 = top_eq (undefined::Maybe Bool) (undefined::Maybe Char) -- test3 :: HTrue test4 = top_eq (undefined::Maybe Bool) (undefined::[Char]) -- test4 :: HFalse test5 = top_eq (undefined::Either Int Char) (undefined::Either Char Int) -- test5 :: HTrue test6 = top_eq (undefined::Either Int Char) (undefined::[Char]) -- test6 :: HFalse -- The following is borrowed from HList and included here for completeness data HTrue data HFalse class TypeCast a b | a -> b, b->a where typeCast :: a -> b class TypeCast' t a b | t a -> b, t b -> a where typeCast' :: t->a->b class TypeCast'' t a b | t a -> b, t b -> a where typeCast'' :: t->a->b instance TypeCast' () a b => TypeCast a b where typeCast x = typeCast' () x instance TypeCast'' t a b => TypeCast' t a b where typeCast' = typeCast'' instance TypeCast'' () a a where typeCast'' _ x = x class TypeEq x y b | x y -> b instance TypeEq x x HTrue instance TypeCast HFalse b => TypeEq x y b

1 0

Squash ladder software in Haskell
by Robin Bate Boerop 21 Nov '06

21 Nov '06

I've recently been looking for some open source software that will enable me to run a squash/tennis/badminton ladder on the Web. I haven't found any. So, it's time to write my own. Haskell is my language of choice. Before I start this project, is there anyone out there who has written some code that might be of use to me? Want to share? -- Robin Bate Boerop

3 2

RFC and Announcement: HLADSPA, LADSPA for Haskell
by Alfonso Acosta 20 Nov '06

20 Nov '06

Hi all, Let me introduce myself. I'm a computer science engineering student, writing his masters thesis about a VHDL translator for ForSyDe (http://www.imit.kth.se/info/FOFU/ForSyDe/ , a Hardware Description Language embedded in Haskell) In order to show a practical application of ForSyDe I decided to try with its audio processing design capabilities. For that purpouse I decided to port LADSPA (http://www.ladspa.org/ ) to Haskell. The result so far is HLADSPA 0.1, which can be downloaded from http://www.student.nada.kth.se/~alfonsoa/HLADSPA-0.1.tgz and contains a testing plugin (Null.hs). It requires GHC>=6.6 due to the use of template haskell and existentially quantified records (read on for more on this). Even for people not interested in LADSPA itself, the project can be regarded as an example of how to create plugins and shared libraries in Haskell without making use hs-plugins. I'll be happy to read any comments and/or questions regarding the project. Here are the design questions on my side: The most important part for creating the HLADSPA, was modelling the LADSPA header file (http://www.ladspa.org/ladspa_sdk/ladspa.h.txt ) in Haskell (http://www.student.nada.kth.se/~alfonsoa/HLADSPA-0.1/HLADSPA.hs ) The essential code snippet is, ===================== -- Existentially quantified records allow the plugin developer -- to chose hd and id types at will and, allowing to declare "heterogeneous" -- Descriptor lists. Drawback: it only works in ghc 6.6 and -- makes the design tricky. The problem comes from modelling (void*) in Haskell -- id is the implementation data data Descriptor = forall id. Descriptor {uniqueID :: LadspaIndex, label :: String, properties :: LadspaProperties, name, maker, copyright :: String, portCount :: LadspaIndex, portDescriptors :: [PortDescriptor], portNames :: [String], portRangeHints :: [PortRangeHint], _implementationData :: id, _instantiate :: Descriptor -> LadspaIndex -> Maybe Instance} -- hd is the handle data Instance = forall hd. Instance { _this :: hd, -- initial handle -- In this case we are using lists to represent the port I/O buffers, so the -- port connections (buffer pointers of ports) is handled by the marshaller -- connectPort :: (hd -> LadspaIndex -> Ptr LadspaData -> IO hd) _activate :: Maybe(hd -> IO ()), -- (LadspaIndex,PortData) indicates the portnumber and its data _run :: hd -> LadspaIndex -> [(LadspaIndex,PortData)] -> ([(LadspaIndex,PortData)], hd), -- Not yet implemented (is not mandatory for a plugin to provide them) -- _runAdding :: -- _setAddingGain :: _deactivate :: Maybe (hd -> IO ()), _cleanup :: hd -> IO () } ===================== This is the best solution I could come up with and I'm not still happy with it. The trickiest part, was modelling (void*) in Haskell. I know that using lists for I/O buffers is inefficient but I coded it having ForSyDe in mind. If people show interest I can code a faster StorableArray-version. Here are my questions. * I'm using GHC's existentially quantified records extension to hide the hd and id parameters because the plugin programmer has to be able to provide a collection of Descriptor (a Descriptor list in current release). I would love to find a solution in plain Haskell98. Any ideas? * This approach requires splitting the original C LADSPA_Descriptor struct in the Descriptor and Instance Haskell types, which leads to a design error: there are functions (e.g. _run, _activate ... ) in Instance which really belong to Descriptor (those functions shouldn't change with the plugin instance). For example, with this approach, it is not possible to tell the plugin host if activate() or deactivate() will be used because this is "asked" any instances is created. * Real Time support in HLADSPA. From LADSPA's documentation: "Property LADSPA_PROPERTY_HARD_RT_CAPABLE indicates that the plugin is capable of running not only in a conventional host but also in a `hard real-time' environment. To qualify for this the plugin must satisfy all of the following: (1) The plugin must not use malloc(), free() or other heap memory management within its run() or run_adding() functions. All new memory used in run() must be managed via the stack. These restrictions only apply to the run() function." Should I forget about HARD_RT_CAPABLE with Haskell? Is there a way to control the use of the heap by a function? * I'm not so sure about the types of _activate, _deactivate and _cleanup. I don't even know if I should include them because they only seem to be required by a language with side effects. Furthermore, _activate() and _deactivate() don't seem to have sense with current implementation cause they are "separated from instantiate() to aid real-time support" and using lists as I/O buffers discards RT support (see above) Thanks in advance for your comments/answers, Alfonso Acosta PS1: Big thanks and claps for the people at #haskell@Freenode . They helped a lot to make this initial release possible. PS2: I would like to get the project hosted at the darcs repository at haskell.org. Do you consider it interesting enough for it?

3 5

importing Distribution.Compat.FilePath fails
by Magnus Therning 20 Nov '06

20 Nov '06

Putting import Distribution.Compat.FilePath in my source results in Could not find module `Distribution.Compat.FilePath': it is hidden (in package Cabal-1.1.6) I want to use 'joinFileName'. I found this thread from the cabal-devel list http://www.mail-archive.com/cabal-devel@haskell.org/msg00162.html and I was hoping that my cabal version would have an unhidden FilePath module... apparently not. Can I unhide it somehow? /M -- Magnus Therning (OpenPGP: 0xAB4DFBA4) magnus(a)therning.org Jabber: magnus.therning(a)gmail.com http://therning.org/magnus Software is not manufactured, it is something you write and publish. Keep Europe free from software patents, we do not want censorship by patent law on written works. It's important for a corporate leader to know the difference between what is actually illegal, and what people assume should be illegal. -- Bill Gates, in interview for The Register, 19th June 2006

5 8

ghci stack overflow
by jim burton 20 Nov '06

20 Nov '06

This code produces a stack overflow in ghci when I call `makeSpiral' with large values, e.g. big enough to produce a 1001x1001 spiral. (makeSpiral produces a list of lists which form a clockwise 'spiral', it's a puzzle from mathschallenge.net.) I'm sure there is a way to increase the stack space in ghc which I will look into, but is there a way I could avoid the problem in the first place by attacking the problem differently? Does stack space run out because the list is an argument being passed around (1001x1001 versions of it)? If so would the state monad help me? data Dir = R | D | L | U deriving (Show, Eq, Enum) type Spiral = ([[Int]], Int, Dir) -- (rows, current row, next direction) rows :: Spiral -> [[Int]] rows (rs, i, d) = rs currentrow :: Spiral -> Int currentrow (rs, i, d) = i nextdir :: Spiral -> Dir nextdir (rs, i, d) = d getrow :: Int -> [[Int]] -> Maybe [Int] getrow i sp = if i < 0 || i >= length sp then Nothing else Just (sp!!i) ndir :: Dir -> Dir ndir d = if d == U then R else succ d newsp :: Spiral newsp = ([[1]], 0, R) makeSpiral :: Int -> Spiral makeSpiral i = makeSpiral' 2 newsp where makeSpiral' j sp = if j > i then sp else makeSpiral' (j+1) (update j sp) update :: Int -> Spiral -> Spiral update i (sp, cr, d) = (sp', cr', d') where oldrow = if (d == U && cr' == cr && cr == 0) || (d == D && cr' == length sp) then [] else fromJust $ getrow cr' sp cr' | d == L || d == R = cr | d == U = if cr == 0 then 0 else cr-1 | otherwise = cr+1 cr'' = if d == U && cr == 0 then -1 else cr' sp' = insertrow cr'' newrow sp newrow = case d of R -> oldrow++[i] D -> oldrow++[i] L -> i:oldrow U -> i:oldrow d' | d == R || d == L = if length oldrow == maximum (map length sp) then ndir d else d | d == U = if cr'' == -1 then ndir d else d | otherwise = if cr' == length sp then ndir d else d insertrow :: Int -> [Int] -> [[Int]] -> [[Int]] insertrow i r rs = if i == -1 then r:rs else front++[r]++back where (front, rest) = splitAt i rs back = if null rest then [] else tail rest printSpiral :: Spiral -> IO () printSpiral (sp, i, d) = putStrLn (concat $ intersperse "\n" (map show sp)) sumdiags :: Spiral -> Int sumdiags (sp, i, d) = (sumdiags' 0 0 (+1)) + (sumdiags' 0 end (subtract 1)) - centre where row1 = sp!!0 end = length row1 - 1 halfx = (length row1 `div` 2) halfy = (length sp `div` 2) centre = (sp!!halfy)!!halfx sumdiags' row col f = if row == length sp then 0 else (sp!!row)!!col + sumdiags' (row+1) (f col) f -- View this message in context: http://www.nabble.com/ghci-stack-overflow-tf2666036.html#a7435185 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

2 1

Collection of objects?
by Valentin Gjorgjioski 20 Nov '06

20 Nov '06

Is some kind of collection of object with different types in Haskell exist? Except the tuples, which have fixed length. I find this * Tuples heterogeneous, lists homogeneous. * Tuples have a fixed length, or at least their length is encoded in their type. That is, two tuples with different lengths will have different types. * Tuples always finite. But I need something which is heterogeneous and non-fixed length. I'm used do Java, and this switch to functional languages is very strange to me. So, to be clear, I need something like LinkedList<Object> in java. Can you please help me or suggest me, what can I use in this case? Valentin

9 12

Yet more type confusion
by chris moline 20 Nov '06

20 Nov '06

Hey all, I'm thoroughly confused by the type error produced by the following: applies a fun returning a tuple of lists to a list of values and then repeatedly applies it to the snd of the result, returning a list of the fst's of successive applications > iterT :: ([a] -> ([a], [a])) -> [a] -> [[a]] > iterT f a = let (b, c) = f a in b : iterT f c like break, but drops the separator > breakDrop :: (a -> Bool) -> [a] -> ([a], [a]) > breakDrop p l = (takeWhile (not . p) l, drop 1 $ dropWhile (not . p) l) like break, but returns a list of lists of values separated by the separator > sep :: (a -> Bool) -> [a] -> [[a]] > sep p = takeWhile (/= "") . iterT (breakDrop p) > main = print $ sep (== 1) "" compling with ghc --make returns this: test.hs:14:45: Couldn't match the rigid variable `a' against `Char' `a' is bound by the type signature for `sep' Expected type: Char -> Bool Inferred type: a -> Bool In the first argument of `breakDrop', namely `p' In the first argument of `iterT', namely `(breakDrop p)' Setting the type signature of sep to (Char -> Bool) -> [Char] -> [[Char]] fixes the problem but I don't get why the signature isn't as general as I think it should be. Something to do with defaulting perhaps? __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com

4 3