January 2007 - Haskell-Cafe

Arrays performance
by paolo.veronelli＠gmail.com 04 Jan '07

04 Jan '07

Good year everyone. I'm timing the following script.I'm not expert to evaluate th O'ness of this code, I hope someone can do it. The program clusters n integers in m buckets based on their distance. Anyway I thing should be linear.So I timed som executions changing the first arg. First argument n is the number of integers to be clustered.Their are choosen randomly between 0 and 100. Second argument m is the number of buckets.For them I choose a value choosen like before. In the timings second argument is always 10. Points Time (ms) 100 40 200 93 400 269 800 831 1600 3063 3200 12693 6400 54708 I'd like to know if the algorithm is the cause for this timings (it's not linear) or if I need to use other kinds of Arrays Thanks Paolino ---------------------------------------------------------------- import Data.Maybe import Data.List import Data.Array.Diff import System.Environment import Control.Monad.State import Control.Arrow import Random inc l i = l // [(i,l!i + 1)] switch l i = l // [(i,not (l!i))] constArray n v = listArray (0,n-1) (repeat v) data CState = CState {clusters :: [(Int,Int)],remi :: Int,colsHeap ::DiffArray Int Int ,rowsFlag :: DiffArray Int Bool} devil [] _ = return () devil (l@(row,col):ls) d = do s@(CState cs r hs fs) <- get let ns = s { clusters = (l:cs), rowsFlag = switch fs row, colsHeap = inc hs col } update | c < d = put ns | (c == d) && (r > 0) = put ns { remi = r - 1 } | otherwise = return () where c = hs ! col when (not (fs ! row)) update devil ls d comp f g x y = (f x) `g` (f y) swap = snd &&& fst collapse = (head &&& unzip) >>> (fst *** snd) mcluster :: [(Int,Int)] -> [(Int,[Int])] mcluster ls = let (lr,lc) = (f *** f) (unzip ls) where f = length.nub -- coo space width (k,r) = divMod lr lc CState cs _ _ _ = execState (devil ls k) CState{clusters = [],remi = r,colsHeap = constArray lc 0,rowsFlag = constArray lr False } in map collapse . groupBy (comp fst (==)) . sort . map swap $ cs coupage ls = zip [0..] ls delta fxy xs ys = [(abs(x-y),(n,m))|(n,x) <- coupage xs, (m,y) <- coupage ys] decoupage ls n = fromJust $ lookup n (coupage ls) test xs ys = let d = snd.unzip.sort $ delta (\x y -> abs (x -y)) xs ys in map (decoupage ys *** map (decoupage xs)) (mcluster d) -- call it with 2 args, the number ov values and the number of clusters -- <prog> 101 10 will cluster 101 values in 10 clusters main = do args <- getArgs gen <- getStdGen let [n,m] = map read args let (ps,bs) = splitAt n (take (m + n) (randomRs (0,100) gen)) print $ test ps bs

4 4

GADT proofs of FunDeps?
by Roberto Zunino 03 Jan '07

03 Jan '07

I am investigating mixing FunDeps with the type equality GADT data Teq a b where Teq :: Teq a a Basically, I would like to write something like proof :: (C a b1, C a b2) => Teq b1 b2 proof = unsafeCoerce# Teq provided the FunDep class C a b | a -> b Is this safe? Any caveat? Regards, Roberto Zunino.

1 0

darcs repo for yampa + gadt
by Joel Reymont 03 Jan '07

03 Jan '07

Folks, I have a version of Yampa with Henrik Nilsson's GADT optimizations that I cleaned up for ghc 6.6 and cabalized. Would it be possible to set it up at darcs.haskell.org and if so how should I go about it? Thanks, Joel -- http://wagerlabs.com/

2 1

State separation/combination pattern question
by Reto Kramer 03 Jan '07

03 Jan '07

I'm looking for a pattern to use for "state separation" in my application. I need to write two "stateful libraries". One is a partitioned in- memory store, the other a disk based store with an in-memory cache fronting it. Both store modules need the IO and State monad. My aim is to write the libraries independently from one another in such a way that they are not aware of the context they will be used in. Both stores are called from a breadth first search loop. The example below extracts the essence of my current approach. foo is function in one of the store modules, bar is from the other type of store. Both manipulate their type of state (StateA, StateB). They extract their slice of the "global" application level state (AppStateRec). What I don't like is that the code in foo and bar know about the AppStateRec and that they need to get the "a", or "b" slot respectively. The store modules should not have such coupling with their client code. I've tried to thread the two states (StateA and StateB) using a chain of StateT ... StateT ..., but couldn't really make that work. It seems rather arbitrary in this case which state to make the inner/ outer one and depending on this ordering the "lifts" have to go with one or the other set of store calls. What I'm really looking for is not so much the chaining of StateT compositions, but rather the isolation of StateA from StateB while they both flow from the search loop into the respective library calls (foo, bar) transparently to the application programmer. I'm hoping there's a way to have the loop be in a State monad whose content is the sum of the two states that are needed for the foo and bar call made to the stores from inside the loop. The calls sites for foo and bar should then extract the right component of the global state and thread only that state through into the modules. Sounds like magic, but how close can I get? I've been unable to find a pattern on the WIKI or the web that refers to this type of "state composition" (or I may not have recognized the match). I trust many of you have run into this and there's an obvious and straight forward best way to address this type of state handling. Thanks, - Reto -------------------------- -- ghci -fglasgow-exts ... -- type StateA = [Integer] type StateB = [Integer] data AppStateRec = AppStateRec { a :: StateA, b :: StateB } deriving Show foo :: MonadState AppStateRec m => m () foo = do st <- get put $ st { a = 1:(a st) } bar :: MonadState AppStateRec m => m () bar = do st <- get put $ st { b = 2:(b st) } type Eval a = StateT AppStateRec Identity a exec :: Eval () exec = do foo bar foo foo bar go = runIdentity $ runStateT exec AppStateRec { a = [], b = [] } Prints: ((),AppStateRec {a = [1,1,1], b = [2,2]})

5 4

Socket Programming
by Mark Goldman 03 Jan '07

03 Jan '07

I am trying to write a toy echo server that can handle multiple connections. I would like to be able to test and see if there are any connections waiting to be accepted on a socket. In C and related languages I would use something like select or poll to be nice to the OS, what would I use with the current haskell libs given that I can't seem to find a function to test if accept would block or not? -mdg -- Our problems are mostly behind us, now all we have to do is fight the solutions.

3 2

Possible (GHC or HGL) bug or ??
by Calvin Smith 03 Jan '07

03 Jan '07

Dear haskell-cafe patrons, I've been working through an exercise in Hudak's _The Haskell School of Expression_ (ex. 3.2, creating a snowflake fractal image), and am seeing some strange drawing behavior that I'm hoping somebody can shed some light on. My initial solution is below (it requires HGL for Graphics.SOE): module Main where import Graphics.SOE main = runGraphics ( do w <- openWindow "Snowflake Fractal" (600, 600) fillStar w 300 125 256 (cycle $ enumFrom Blue) spaceClose w ) spaceClose w = do k <- getKey w if k == ' ' then closeWindow w else spaceClose w minSize = 2 :: Int fillStar :: Window -> Int -> Int -> Int -> [Color] -> IO () fillStar w x y h clrs | h <= minSize = return () fillStar w x y h clrs = do drawInWindow w (withColor (head clrs) (polygon [t1p1,t1p2,t1p3,t1p1])) drawInWindow w (withColor (head clrs) (polygon [t2p1,t2p2,t2p3,t2p1])) sequence_ $ map recur [t1p1,t1p2,t1p3,t2p1,t2p2,t2p3] where tanPiOverSix = tan(pi/6) :: Float halfSide = truncate $ tanPiOverSix * fromIntegral h hFrag = truncate $ tanPiOverSix * tanPiOverSix * fromIntegral h (t1p1,t1p2,t1p3) = ((x, y), (x-halfSide, y+h),(x+halfSide, y+h)) (t2p1,t2p2,t2p3) = ((x-halfSide, y+hFrag),(x, y+h+hFrag),(x+halfSide, y+hFrag)) reVert y = y - ((h - hFrag) `div` 3) recur pnt = fillStar w (fst pnt) (reVert (snd pnt)) (h`div`3) (tail clrs) This basically works, in that it does exactly what I want in Hugs, but GHC sometimes pauses partway through rendering, and does not continue rendering until I type any key (except space, which exits) or unfocus/refocus the window, or move the mouse pointer across the window. Sometimes, more often the first time in a GHCI session, it renders completely with no pauses, and it seems to pause more and more if I evaluate main, then close the window, evaluate again in the same GHCI session, repeatedly. The same pausing behavior is observed in a GHC-compiled executable. When the problem occurs, there is a message to the console that says: "thread blocked indefinitely". Versioning info: CPU: Pentium M OS: Gentoo GNU/Linux, kernel 2.6.18 GCC: 4.1.1 GHC: 6.6 HGL: 3.1 HUGS: March 2005 [all software compiled from source using gentoo ebuilds] Is anybody else familiar with this behavior? If not, any suggestions as to where I should file this as a potential bug? GHC? HGL? Both? Elsewhere? Thanks in advance for any information. Calvin p.s. Any stylistic or other comments about the code welcome too.

2 2

Extensible static checking of dimensions?
by Mike Gunter 02 Jan '07

02 Jan '07

The very nice Buckwalter and Denney dimensional-numbers packages both work on a fixed set of base dimensions. This is a significant restriction for me--I want to avoid adding apples to oranges as well as avoiding adding meters to grams. Is it possible to have an extensible set of base dimensions? If so, how usable can such a system be made? Is it very much worse than a system with a fixed set of base dimensions? thanks, -m

1 0

Generating Source Code with Haskell
by Martin Huschenbett 02 Jan '07

02 Jan '07

Hi, my aim is to transform an XML file into C++ source code with a Haskell program. The part that parses the XML is already finished (using HaXML) but the part that generates the C++ code is still remaining. Is there already any work on this topic? Maybe even on generating Java or any other object oriented or imperative language. My first approach was to simply generate the C++ code as text using a pretty printing library but this becomes ugly very fast. Next I thought about generating and rendering the AST of the resulting C++ code. But I don't want to reinvent the wheel. Regards, Martin.

2 1

Glasgow Distributed Haskell
by Joel Reymont 02 Jan '07

02 Jan '07

Is anyone using GdH? Can someone tell me why it's not part of the GHC distribution? It seems that GdH is not being developed anymore and I think it's a real pity! Thanks, Joel -- http://wagerlabs.com/

3 4

Re: [Haskell-cafe] Composing functions with runST
by Yitzchak Gale 02 Jan '07

02 Jan '07

Hi Thomas, You wrote: > How do I "import" Control.Monad.ST so I can experiment with it from > ghci and just do > runST > like you had. Instead of qualifying it in some way. In GHCi, use the :module command (:m) for built-in modules, and :load and :add for source files. In Hugs, use :load and :also for both. You need to run Hugs with the -98 flag to use Control.Monad.ST. > how do I do runST as fully qualified? Like this: Prelude> Control.Monad.ST.runST (do {r <- Data.STRef.newSTRef 2007; Data.STRef.readSTRef r}) 2007 Have fun with monads! Regards, Yitz

1 0