- Haskell-Cafe - Haskell.org

Haskell vs Ruby as a scripting language
by Joel Reymont 22 Feb '07

22 Feb '07

Is anyone using Haskell as a scripting language in their app? I'm thinking of viable it would be to embed ghc in a Mac (Cocoa) app. TextMate [1] uses Ruby as the extension language and quite successfully at that. Everybody loves Ruby since it's simple. I need a trading systems language and I'm afraid the combination of ... everything that makes Haskell otherwise great will prove a drawback in my case. What do you think? Thanks, Joel [1] http://macromates.com/ -- http://wagerlabs.com/

7 12

Debugging concurrent program - no threads apparently running, but RTS still doing something.
by Alistair Bayley 22 Feb '07

22 Feb '07

Below is a test case for a threading problem I can't figure out. It models a socket server (here I've replaced the socket with an MVar, to keep it simple). The idea is to have a listener which accepts incoming requests on the socket. When one arrives, it forks a handler thread to deal with the request, and returns to listening on the socket. The handler thread is run in parallel with a timeout thread. In the test case below, the handler takes too long, so the timeout thread completes and kills the handler. The problem is that when the main thread ends, the RTS doesn't stop for another 6 or so seconds. The only thread that runs this long is the handler (waitFor (secs 8.0)) but it has already been killed. So I'm scratching my head a bit. Also, any pointers to better techniques for designing and debugging concurrent code are appreciated (is there a better way than putStrLn?) Platform: ghc-6.6, Windows XP. Thanks, Alistair --------------------------------------------------------------------- module Main where import Prelude hiding (catch) import Control.Concurrent import Control.Exception import System.IO secs :: Float -> Int secs n = round (n * 1000000) -- e.g. waitFor (secs 25) waitFor n = debug ("waitFor start " ++ show ((fromIntegral n) / 1000000.0)) >> threadDelay n >> debug ("waitFor end " ++ show ((fromIntegral n) / 1000000.0)) debug msg = myThreadId >>= ( \t -> putStrLn $ (show t) ++ ": " ++ msg ) -- Thread 1 - start server then send message main = do hSetBuffering stdout LineBuffering blockingInput <- newEmptyMVar -- like a socket; accept on a socket blocks listnr <- forkIO (listener blockingInput) putMVar blockingInput "hello" waitFor (secs 2.0) debug "main: done" -- Thread 2 - listener. -- Blocks on input; when input arrives, starts handler thread. listener blockingInput = do msg <- takeMVar blockingInput serveRequest msg -- in a real server we'd loop: --listener blockingInput debug "listener: done" -- Start threads 3 and 4 - handler and timeout. serveRequest msg = do let acquire = return () let release _ = debug "handler release action" forkIO (runTimeout 0.1 acquire release (handler msg)) return () handler msg _ = do debug ("handler start: " ++ msg) catch (waitFor (secs 8.0) >> debug "handler end") (\e -> debug ("Exception: " ++ (show e)) >> throwIO e) runTimeout timeout acquire release action = do handlerTid <- myThreadId -- Use this to ensure the timeout thread doesn't start before the handler -- i.e. give the handler a chance to start. startTimeout <- newEmptyMVar timeoutTid <- forkIO (runTimeoutThread startTimeout timeout handlerTid) bracket acquire ( \a -> release a >> killThread timeoutTid ) ( \a -> do debug "runTimeout: start handler action" putMVar startTimeout True action a debug "runTimeout: end handler action" ) runTimeoutThread startTimeout timeout handlerTid = do takeMVar startTimeout debug "runTimeoutThread: start" waitFor (secs timeout) killThread handlerTid debug "runTimeoutThread: end"

2 2

Re: Leaves of a Tree
by Chad Scherrer 22 Feb '07

22 Feb '07

Neil, I think this idea is better than what I had suggested, but as it stands it doesn't typecheck. Did you mean something like this? leaves :: Tree -> [Int] leaves = f [] where f rest (Leaf n) = n : rest f rest (Branch l r) = f (f rest r) l -Chad ------------------------------- (from Neil Mitchell) Hi Tom > data Tree = Branch Tree Tree | Leaf Int deriving (Eq, Ord) > leaves :: Tree -> Set Int > leaves (Leaf n) = singleton n > leaves (Branch left right) = union (leaves left) (leaves right) The standard method for a traversal over leaves with accumulation is: leaves :: Tree -> Set Int leaves x = f [] where f (Leaf n) rest = n : rest f (Branch l r) rest = f l (f r rest) This makes the construction of the list quite cheap. Then you can do the fromList trick, and that might give you a speed up. Thanks Neil

2 1

Leaves of a Tree
by Tom Hawkins 22 Feb '07

22 Feb '07

Hello, Any recommendations for speeding up extracting the set of leaves from a tree? data Tree = Branch Tree Tree | Leaf Int deriving (Eq, Ord) My slow, naive function: leaves :: Tree -> Set Int leaves (Leaf n) = singleton n leaves (Branch left right) = union (leaves left) (leaves right) In my case, many of the branches in the tree are the same. I suspect the fixed point operation mentioned in the thread "speeding up fibonacci with memoizing" is applicable, but I'm having a tough time making the connection. -Tom

6 5

Selecting overlapping instances
by Emil Axelsson 22 Feb '07

22 Feb '07

Hello! I have a problem with overlapping instances for which I already know a workaround. However, I'm still curious to know if there isn't a simpler solution available. I have a feeling that -fallow-incoherent-instances might be the answer, but I can't get it to work. In the code at the end of the message, (Block w n s e) is a representation of a geometrical block whose west-/north-/south-/eastern edge has type w/n/s/e respectively. (*||*) composes two blocks horizontally and (*=*) composes vertically. In this simplified example, there is only one primitive block -- unitBlock. Now, I want to be able to make grids of unitBlock:s where the edges can have any type that can be obtained using (,) and (). This is what the Grid class attempts. The program compiles fine until I add the test program > test :: Block ((),()) ((),()) ((),()) ((),()) > test = grid which raises an "Overlapping instances" error. What I would like is for the compiler to pick *either* of the two matching instances first, and then the other one, because in this particular case, it doesn't matter which one it picks first. The workaround is to explicitly pick an order by giving the additional instance (requires -fallow-overlapping-instances): > instance ( Grid x1 y1 > , Grid x1 y2 > , Grid x2 y1 > , Grid x2 y2 > ) => Grid (x1,x2) (y1,y2) > where > grid = grid *||* grid Is there any way to make this work without adding this last instance? Thanks! / Emil -------------------------------------------------------- > data Block w n s e = Block > > (*||*) :: Block w1 n1 s1 x -> Block x n2 s2 e2 -> Block w1 (n1,n2) (s1,s2) e2 > (*||*) = undefined > > (*=*) :: Block w1 x s1 e1 -> Block w2 n2 x e2 -> Block (w1,w2) n2 s1 (e1,e2) > (*=*) = undefined > > unitBlock :: Block () () () () > unitBlock = undefined > > class Grid x y > where > grid :: Block x y y x > > instance Grid () () > where > grid = unitBlock > > instance (Grid x1 y, Grid x2 y) => Grid (x1,x2) y > where > grid = grid *=* grid > > instance (Grid x y1, Grid x y2) => Grid x (y1,y2) > where > grid = grid *||* grid

1 0

Re: Leaves of a Tree
by Chad Scherrer 21 Feb '07

21 Feb '07

Hi Tom, Tom Hawkins wrote: > Folding was my first approach: > > leaves :: Tree -> Set Int > leaves tree = accumLeaves Set.empty tree > > accumLeaves :: Set Int -> Tree -> Set Int > accumLeaves set (Leaf n) = insert n set > accumLeaves set (Branch l r) = foldl accumLeaves set [l,r] > > However, with this approach I quickly ran out of stack space. I found > this odd, since I thought this program was tail recursive and > shouldn't be using the stack. This is a problem of tail recursion and lazy evaluation not playing nicely. See this page: http://www.haskell.org/haskellwiki/Stack_overflow > My next attempt was to use some form of memorization. Since many of > the branches in my trees are equal, memorization should prevent > following branches that have already been calculated. My question is, > what is the best way to transform the original function to incorporate > memorization? I think something like this could be done, if there's some invariants maintained by the data structure. Is there any additional structure you're imposing beyond that required for the "data" line? -Chad

1 0

Type-level lambdas in Haskell? ( was Multiparameter class error)
by oleg＠pobox.com 21 Feb '07

21 Feb '07

Alfonso Acosta wrote: > class Synchronous s f1 f2 | s -> f1, s -> f2 where > mapSY :: f1 a b -> s a -> s b > delaySY :: a -> s a -> s a > zipWithSY :: f2 a b c-> s a -> s b -> s c > > The goal of this class is to extend the name of the following > functions (which BTW are already present in a working library and for > that reason _it is a must_ that their types remain untouched) ... > > mapSY :: (a->b) -> Signal a -> Signal b > delaySY :: a -> Signal a -> Signal b -> Signal c > zipWithSY :: (a->b->c) -> Signal a -> Signal b -> Signal c > > .. accepting these definitions as well > > mapSY :: (HDPrimType a, HDPrimType b) => > HDFun (a->b) -> HDSignal a -> HDSignal b > delaySY :: HDPrimType a => a -> HDSignal a -> HDSignal a > zipWithSY :: (HDPrimType a, HDPrimType b, HDPrimType c) => HDFun > (a->b->c) -> HDSignal a -> HDSignal b -> HDSignal c First of all, the design already exhibits the problem: delaySY :: HDPrimType a => a -> HDSignal a -> HDSignal a cannot be made _at all_ the member of an instantiated Synchronous class. The reason is that in the class definition > class Synchronous s f1 f2 | s -> f1, s -> f2 where > delaySY :: a -> s a -> s a the function delaySY is declared *fully* polymorphic over 'a' -- there are no constraints on a and no restrictions. However, > delaySY :: HDPrimType a => a -> HDSignal a -> HDSignal a shows that 'a' is constrained to satisfy the HDPrimType a. That's the problem: the latter function is not generic enough. The problem is described (and solved) in a message `Restricted Datatypes Now' http://www.haskell.org/pipermail/haskell-prime/2006-February/000498.html I'm not certain if there is a compelling reason to place mapSY, delaySY and zipWithSY in the same class. If not, the following is the solution to the problem. Both sets of mapSY, delaySY and zipWithSY are unified in overloaded functions: {-# OPTIONS -fglasgow-exts -fallow-undecidable-instances #-} module SY where class SynchronousM arg1 s a b | s a b -> arg1 where mapSY :: arg1 -> s a -> s b class SynchronousD s a where delaySY :: a -> s a -> s a class SynchronousZ arg1 s a b c | s a b c -> arg1 where zipWithSY :: arg1 -> s a -> s b -> s c -- stubs newtype Signal a = Signal a newtype HDSignal a = HDSignal a newtype HDFun a = HDFun a class HDPrimType a where cnv :: a -> a; cnv = id instance HDPrimType Int instance HDPrimType Bool -- (not so) Grand Unification instance SynchronousM (a->b) Signal a b where mapSY f (Signal x) = Signal (f x) instance (HDPrimType a, HDPrimType b) => SynchronousM (HDFun (a->b)) HDSignal a b where mapSY (HDFun f) (HDSignal x) = HDSignal (cnv . f . cnv $ x) instance SynchronousD Signal a where delaySY _ = id instance HDPrimType a => SynchronousD HDSignal a where delaySY _ (HDSignal x) = HDSignal (cnv x) instance SynchronousZ (a->b->c) Signal a b c where zipWithSY f (Signal x) (Signal y) = Signal (f x y) instance (HDPrimType a, HDPrimType b, HDPrimType c) => SynchronousZ (HDFun (a->b->c)) HDSignal a b c where zipWithSY (HDFun f) (HDSignal x) (HDSignal y) = HDSignal (cnv (f (cnv x) (cnv y)))

2 1

Is anyone using CUDA with haskell yet?
by Jefferson Heard 21 Feb '07

21 Feb '07

I don't want to duplicate anyone's work, and I'm not sure that NDA would allow me to release the code in any case (have to check on it carefully), but is anyone currently using the CUDA framework from nVidia inside of Haskell for highly parallel programming? -- Jeff

1 0

Re: Leaves of a Tree
by Chad Scherrer 21 Feb '07

21 Feb '07

Tom, I think inserting elements would be a lot faster than multiple unions. I would try: leafList :: Tree -> [Int] leafList (Leaf n) = [n] leafList (Branch left right) = leafList left ++ leafList right leaves = fromList . leafList If you're writing many functions on Trees (or maybe even if you're not), you might consider writing a fold function and putting leafList in terms of this. Do you have experience with folds? -Chad > Hello, > > Any recommendations for speeding up extracting the set of leaves from a tree? > > data Tree = Branch Tree Tree | Leaf Int deriving (Eq, Ord) > > My slow, naive function: > > leaves :: Tree -> Set Int > leaves (Leaf n) = singleton n > leaves (Branch left right) = union (leaves left) (leaves right) > > In my case, many of the branches in the tree are the same. I suspect > the fixed point operation mentioned in the thread "speeding up > fibonacci with memoizing" is applicable, but I'm having a tough time > making the connection. > > -Tom

2 1

Type-level lambdas in Haskell?
by oleg＠pobox.com 21 Feb '07

21 Feb '07

On 2/21/07, Alfonso Acosta <alfonso.acosta at gmail.com> wrote: > In my opinion adding Type-level lambdas would be the way to go, but > they unfortunately are not part of Haskell. Type-level lambdas are already present in Haskell. Please see the messages On computable types. I. Typed lambda and type closures http://www.haskell.org/pipermail/haskell/2006-September/018486.html On computable types. II. Flipping the arrow http://www.haskell.org/pipermail/haskell/2006-September/018487.html

1 0