- Haskell-Cafe - Haskell.org

Why are new releases of libraries required for every GHC release?
by DavidA 22 Nov '06

22 Nov '06

Some recent comments suggested that every time there is a new GHC release, there needs to be a new wxHaskell release (or insert name of other library here) to work with it. This seems to be true even for minor upgrades, like 6.4.1 -> 6.4.2. Why is this? Does GHC break binary compatibility at every release? Is this avoidable? This makes using Haskell unnecessarily hard compared to other platforms.

4 3

help with threadDelay
by Neil Davies 22 Nov '06

22 Nov '06

Hi, I'm using GHC 6.6 (debian/etch) - and having some fun with threadDelay. When compiled without the -threaded compiler argument it "behaves" as documented - waits at least the interval - for example: Tgt/Actual = 0.000000/0.036174s, diff = 0.036174s Tgt/Actual = 0.000001/0.049385s, diff = 0.049384s Tgt/Actual = 0.000005/0.049492s, diff = 0.049487s Tgt/Actual = 0.000025/0.049596s, diff = 0.049571s Tgt/Actual = 0.000125/0.049655s, diff = 0.04953s Tgt/Actual = 0.000625/0.04969s, diff = 0.049065s Tgt/Actual = 0.003125/0.049684s, diff = 0.046559s Tgt/Actual = 0.015625/0.04962s, diff = 0.033995s Tgt/Actual = 0.078125/0.099668s, diff = 0.021543s Tgt/Actual = 0.390625/0.399637s, diff = 0.009012s Tgt/Actual = 1.953125/1.999515s, diff = 0.04639s Tgt/Actual = 9.765625/9.799505s, diff = 0.03388s however when -threaded is used you get some interesting effects, including returning too early: Tgt/Actual = 0.000000/0.000093s, diff = 0.000093s Tgt/Actual = 0.000001/0.000031s, diff = 0.00003s Tgt/Actual = 0.000005/0.000029s, diff = 0.000024s Tgt/Actual = 0.000025/0.000028s, diff = 0.000003s Tgt/Actual = 0.000125/0.000034s, diff = -0.000091s Tgt/Actual = 0.000625/0.000035s, diff = -0.00059s Tgt/Actual = 0.003125/0.000029s, diff = -0.003096s Tgt/Actual = 0.015625/0.000028s, diff = -0.015597s Tgt/Actual = 0.078125/0.058525s, diff = -0.0196s Tgt/Actual = 0.390625/0.389669s, diff = -0.000956s Tgt/Actual = 1.953125/1.939513s, diff = -0.013612s Tgt/Actual = 9.765625/9.749573s, diff = -0.016052s The program I used to generate this is :- import Control.Concurrent import Data.Time import Text.Printf main = mapM_ delay (0 : take 11 (iterate (*5) 1)) delay n = do tS <- getCurrentTime threadDelay n tE <- getCurrentTime let n' = toRational n / 10^6 n'' = fromRational (n') :: Double obs = diffUTCTime tE tS printf "Tgt/Actual = %0.6f/%s, diff = %s\n" n'' (show obs) (show $ obs - fromRational n') return () Any suggestions? Neil

3 2

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 21 Nov '06

21 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