- Haskell-Cafe - Haskell.org

functional database queries
by Henning Thielemann 22 Feb '07

22 Feb '07

At http://www.haskell.org/hawiki/HaskellDbTutorial it is described, how database queries can be modelled with a monad. However, I wonder if this is also possible without monads. Say, writing "DB.map col1 $ DB.filter (\row -> col2 row == 10+2) myTable" for "SELECT col1 FROM MyTable where col2 = 10+2"

4 8

TFP 2007: Registration and Program
by TFP 2007 22 Feb '07

22 Feb '07

Dear Colleagues, You may now resgister for TFP 2007! TFP 2007 will be held April 2-4, 2007 in New York City, USA. Our invited speaker is John McCarthy, Stanford University. Further details can be found at our homepage: http://cs.shu.edu/tfp2007/ . You may register at: http://cs.shu.edu/tfp2007/registration.html . The registration deadline is March 2, 2007 (11:59 p.m. EST). Accomodations information may be found at: http://cs.shu.edu/tfp2007/accomodations.html . We kindly remind you that the deadline to make a hotel reservation at the guaranteed rates offered to TFP 2007 participants is also quickly approaching. We are proud to announce our program of accepted talks: Unifying Hybrid Types and Contracts Jessica Gronski and Cormac Flanagan A Dual Semantics for the Data Description Calculus Yitzhak Mandelbaum, Kathleen Fisher, and David Walker A Metalanguage for Structural Operational Semantics Matthew Lakin and Andrew Pitts An Arrow Based Semantics for Interactive Applications Peter Achten, Marko van Eekelen, Maarten de Mol, and Rinus Plasmeijer Dependent Types: Easy as Pie Dimitrios Vytiniotis and Stephanie Weirich Constructing Correct Circuits -- Hardware Modelling with Dependent Types Edwin Brady, James McKinna, and Kevin Hammond Why Would Extensible Dependent Types Matter Pablo Nogueira and Bruno Oliveira Bytecode Verification for Haskell Robert Dockins and Samuel Z. Guyer UnreadTVar: Extending Haskell Software Transactional Memory for Performance Nehir Sonmez, Cristian Perfumo, Srdjan Stipic, Adrian Cristal, Osman S. Unsal, and Mateo Valero A New Functional Implementation of Grover's Fast Search Algorithm Justin Stallard and Murray Gross An Inference Algorithm for Guaranteeing Safe Destruction Manuel Montenegro, Ricardo Peña, and Clara Segura Hierarchical Master/Worker Skeletons Jost Berthold, Mischa Dieterle, Rita Loogen, and Steffen Priebe Property Directed Generation of First-Order Test Data Fredrik Lindblad Refactoring for Comprehension Gustavo Villavicencio Towards a Box Calculus for Hume Gudmund Grov and Greg Michaelson Scaled Regression: A Refinement of Primitive Recursion Daniel Leivant Equality-Based Uniqueness Typing Edsko de Vries, Rinus Plasmeijer, and David Abrahamson Lightweight Static Resources: Sexy Types for Embedded and Systems Programming Oleg Kiselyov and Chung-chieh Shan Space-Efficient Gradual Typing David Herman, Aaron Tomb, and Cormac Flanagan Use-Based Reference of Polymorphism Dave King and John Hannan Designing a Generic Graph Library Using ML Functors Sylvain Conchon, Jean-Christophe Filliatre, and Julien Signoles The SCIence Joint Research Activity Kevin Hammond, Dana Petcu, Phil Trinder, Abdallah Al Zain, Steve Linton, and Greg Michaelson Generic and Index Programming Jeremy Gibbons, Meng Wang, and Bruno C d. S. Oliveira The AHA Project Marko van Eekelen, Olha Shkaravska, Ron van Kesteren, Bart Jacobs, Sjaak Smetsers, and Erik Poll Studying Helium Program Bahaviour with the Neon Library Jurriaan Hage and Peter van Keeken Design and Implementation of JFP Hao Xu Hop Client-Side Compilation Florian Loitsch Adaptive High-Level Scheduling in a Generic Parallel Runtime Environment Jost Berthold, Abyd Al-Zain, and Hans-Wolfgang Loidl Bundles Pack Tighter than Lists Francisco Lopez-Fraguas, Juan Rodriguez-Hortala, and Jaime Sanchez-Hernandez Model-Based Testing of Thin-Client Web Applications and Navigation Input Pieter Koopman, Peter Achten, and Rinus Plasmeijer We look forward to seeing you at TFP 2007! Cheers, Marco ************************************************************************************ Dr. Marco T. Morazan TFP 2007 Program Committee Chair http://cs.shu.edu/tfp2007/

3 4

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 22 Feb '07

22 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 22 Feb '07

22 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 22 Feb '07

22 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