- Haskell-Cafe - Haskell.org

Troubles understanding memoization in SOE
by Peter Verswyvelen 27 Sep '07

27 Sep '07

Hi, in SOE, the following memoization function is implemented: memo1 :: (a->b) -> (a->b) memo1 f = unsafePerformIO $ do cache <- newIORef [] return $ \x -> unsafePerformIO $ do vals <- readIORef cache case x `inCache` vals of Nothing -> do let y = f x writeIORef cache [(x,y)] -- ((x,y) : -- if null vals then [] else [head vals]) return y Just y -> do return y inCache :: a -> [(a,b)] -> Maybe b x `inCache` [] = Nothing x `inCache` ((x',y'):xys) = if unsafePtrEq x x' then Just y' else x `inCache` xys This is then used in type Time = Float type UserAction = G.Event data G.Event = Key Char Bool | Button Point Bool Bool | MouseMove Point | Resize | Closed deriving Show newtype Behavior a = Behavior (([Maybe UserAction],[Time]) -> [a]) newtype Event a = Event (([Maybe UserAction],[Time]) -> [Maybe a]) Behavior fb `untilB` Event fe = memoB $ Behavior (\uts@(us,ts) -> loop us ts (fe uts) (fb uts)) where loop (_:us) (_:ts) ~(e:es) (b:bs) = b : case e of Nothing -> loop us ts es bs Just (Behavior fb') -> fb' (us,ts) memoB :: Behavior a -> Behavior a memoB (Behavior fb) = Behavior (memo1 fb) If I understand it correctly, the memoization is required because otherwise recursive "streams" wouldn't work. For example, in the Pong game example, a ballPositionX stream is generated by integrating a ballVelocityX stream, but the ballVelocityX stream changes sign when the ball hits the left or right walls, and to determine that event, the ballPositionX stream is required. So both streams are mutually recursive, and without memoization, the program would be stuck (at least my own FRP experiments, which don't use memoization yet, gets stuck :-)). Another trick to prevent this, is the "b : case e of" code in untilB, which causes the event to be handled a bit too late, to avoid cyclic interdependencies. I hope I got that right. Now my questions. So, the keys (x) and values (y) in (memo1 fb) are streams (aka infinite lists)? More correctly, memo1 uses a pointer to the head of the list as a key, for fast comparing (as you can't compare infinite lists)? But since both key and value are infinite streams, won't this approach cause a serious space leak because the whole list cannot be reclaimed by the garbage collector? So the full ballPositionX and ballVelocityX streams would remain in memory, until the program exits? Since this doesn't happen when I run the SOE examples (I guess!), I clearly misunderstand this whole thing. I could explain it when the pointer to the list is actually a pointer to the delayed computation (a "thunk"?) of the tail, but the code doesn't seem to do that. Thanks for any help, I hope I explained the problem well enough. Peter Verswyvelen

9 16

YI on Windows?
by Peter Verswyvelen 26 Sep '07

26 Sep '07

I retrieved the latest version of YI, but I failed to compile it for Windows (GHC 6.6.1, and I got alex-2.1.0, haddock-0.8, HsColour, GTK, but not VTY) Before even pasting the error log, is it supported in Windows? I see that "make" gave the error "ghc.exe: unknown package: unix" and some more errors. "make emacs" worked better, but failed starting "dist/build/yi/yi -B. -fgtk --as=emacs" with the error "\driver\package.conf.inplaceonf as c:\app\ghc" Thanks, Peter BTW: I was using MinGW/Msys

2 1

Does Haddock respect hiding?
by Adrian Hey 26 Sep '07

26 Sep '07

Hello folks, Using Haddock 0.8, if I use haddock to document a module like this.. module MyModule ( module MyOtherModule ) where import MyOtherModule hiding (foo) I still get foo documented in the API for MyModule, despite the fact that foo is not really made available by importing MyModule. This looks like a bug to me, or maybe there's something else I should be doing. Anyone care to comment? Thanks -- Adrian Hey

1 0

GHC 6.7 on Windows / containers-0.1 package?
by Peter Verswyvelen 26 Sep '07

26 Sep '07

Since I'm hopelessly stuck with an weird infinite loop (that consumes 0% CPU time!), and since I can't find the problem using "trace", I wanted to try GHC 6.7, which seems to container a debugger (woohoo!!!). Currently I'm using GHC-6.6.1 on Windows. So I grabbed ghc-6.7.20070824 (=the latest one for Windows I could find) and the "extra-libs", compiled and installed the GLUT package (which I needed), but when I compile my library, I get Could not find module `Data.Map': it is a member of package containers-0.1, which is hidden So I tried to expose it using GHC-PKG expose containers-0.1 which worked find, because GHC-PKG list prints d:/app/ghc/ghc-6.7.20070824\package.conf: Cabal-1.1.7, GLUT-2.1.1, HUnit-1.1.1, OpenGL-2.2.1, QuickCheck-1.0.1, Win32-2.1, array-0.1, arrows-0.2.1, base-2.1, bytestring-0.1, cgi-3001.1.5, containers-0.1, directory-1.0, fgl-5.4.1, filepath-1.0, (ghc-6.7.20070824), haskell-src-1.0.1, haskell98-1.0, hpc-0.5, html-1.0.1, mtl-1.0.1, network-2.0.1, old-locale-1.0, old-time-1.0, packedstring-0.1, parallel-1.0, parsec-2.0, pretty-1.0, process-1.0, random-1.0, regex-base-0.72, rts-1.0, stm-2.1, template-haskell-0.1, xhtml-3000.0.2 Anybody has an idea how I can continue? Thanks (again!), Peter

7 12

C's fmod in Haskell
by Peter Verswyvelen 26 Sep '07

26 Sep '07

Maybe this is a stupid question, but I don't find something similar in Haskell. I find mod and rem, which work on integers. But I'm looking for a function similar to C's fmod. Of course I can write it myself, but I guess it must already exist under a different name? Thanks, Peter

6 10

Re: Math.Statistics
by ok 26 Sep '07

26 Sep '07

There are a number of interesting issues raised by mbeddoe's Math.Statistics. 0. Coding issues. Why use foldr1 (*) instead of product? covm xs = split' (length xs) cs where cs = [ cov a b | a <- xs, b <- xs] split' n = unfoldr (\y -> if null y then Nothing else Just $ splitAt n y) seems a rather odd way to write covm xs = [[cov a b | b <- xs] | a <- xs] which in turn is a bit wasteful because the matrix must be symmetric. I believe the author may have misunderstood "numerically stable". The obvious (sum xs)/(fromIntegral $ length $ xs) is fine for the mean, and the obvious two-pass algorithm for the variance is fine. The tricky algorithms are needed for incremental one-pass calculation. 1. How do you decide how general to make things? mean, hmean: Floating a But only + and / are needed, so Fractional a is enough. gmean: Floating a You need + and /, so fair enough. median: Floating a, Ord a High median and low median (not provided) need only Ord a. Standard median needs + and /, so fair enough. modes: Ord a Right. range: Num a, Ord a But range needs only Ord a. avgdev: Floating a Right. pvar, var, stddev, skew, kurtosis, cov, covm: Floating a How should one define the variance of a collection of complex numbers? I'm not at all sure that it makes sense. If I were dealing with complex numbers, I might treat them as 2-vectors, in which case the "standard deviation" would be a 2x2 matrix, not a complex number. I suspect that these should require Floating a, Ord a. For skew this is quite certain: one looks for "positive" or "negative" skew, and this makes no sense for complex numbers. iqr: type not specified but appears to be :: [a] -> [a] This is certainly the wrong type as the inter-quartile range is supposed to be a NUMBER, not a sequence. You have to use comparisons and subtraction, so iqr :: Num a, Ord a => [a] -> a 2. Statistics This is an odd bunch of things; mostly things that are dangerous to use. A collection of the techniques from "Applications, Basics, and Computing" by Hoaglin and Velleman (and was there someone else? memory fails me) would be nice. A few basic robust measures like - median absolute deviation - trimmed mean - Winsorized standard deviation - percentage bend correlation might be nice. 3. How laziness could help. Suppose you ask for the mean, standard deviation, and skewness of a bunch of numbers using this library. Calculating the standard deviation will recalculate the mean. Calculating the skewness will recalculate the standard deviation, which will recalculate the mean. Robust statistics, like the trimmed mean, often want to sort the data. And you don't want to keep on sorting the data over and over again. This is a case where Haskell's laziness really shines: it translates into direct practical gains for simple code. data (Floating a, Ord a) => Simple_Continuous_Variate a = SCV [a] Int a a (Array Int a) list_to_variate xs = SCV xs n m s o where n = length xs m = sum xs / fromIntegral n s = sum [(x - m)^2 | x <- xs] / fromIntegral (n - 1) o = listArray (1,n) (sort xs) vLength (SCV _ n _ _ _) = n vMean (SCV _ _ m _ _) = m vSd (SCV _ _ _ s _) = s vMin (SCV _ _ _ _ a) = a ! 1 vMax (SCV _ n _ _ a) = a ! n vRange scv = vMax scv - vMin scv vMedian (SCV _ n _ _ a) | odd n = a ! ((n+1)`div`2) | even n = ((a ! l) + (a ! u))/2 where l = n `div` 2 u = n - l ..... The wonderful thing about this is that there are no bangs in SCV, so the various pieces of information don't get evaluated until they are needed, and then don't get evaluated *again*. For example, vRange will cause the sorted array to be built at most once. Trimmed mean is very little harder to write than vMedian. Esoteric uses of lazy evaluation abound, but this one makes sense even to an old number-crunching programmer. I once built something like this in C, but boy, it was a pain.

4 4

Pierce on type theory and category theory
by Seth Gordon 26 Sep '07

26 Sep '07

Are Benjamin C. Pierce's _Types and Programming Languages_ and/or _Basic Category Theory for Computer Scientists_ suitable for self-study? (Do they have problem sets that can be checked by either looking up answers in The Back of the Book, or by trying to compile/run some code that the student writes?) FWIW, my formal math education--well, all the formal math education that I can remember at this point--stopped at freshman calculus plus one semester of statistics.

9 8

Re: [Haskell-cafe] PROPOSAL: Rename haskell@ to haskell-announce@
by Andrzej Jaworski 26 Sep '07

26 Sep '07

Flooding haskell-cafe with extra traffic from haskel@ will lead to comp.soft-sys.matlab syndrom where few people read anything but their own postings and discussion is virtually unknown. I can see only two options available to us right now to preserve readability in the fast growing Haskell community: divide haskell@ into more specific lists (haskell-cafe should preserve its right to long threads !!!) or ascribe volunteers (on monthly bases) to moderate and process haskell@ so as to receive tagged tree of links. -A.J.

3 2

Re: [Haskell-cafe] Composition Operator
by PR Stanley 26 Sep '07

26 Sep '07

Ah, I understand now. Let me get this right: The resulting (a -> c) is a kind of abstract function formed by the pairing of <a -> b) and (b -> c), hence the lambda \x -> g (f x), correct? Thanks, Paul At 05:11 22/09/2007, you wrote: >Hello, > >It's probably easiest to think of composition as a function which >takes two arguments (both functions), (g :: b -> c) and (f :: a -> b), >and returns a new function of type a -> c. We could write this >explicitly as > > composition :: (b -> c, a -> b) -> a -> c > composition (g,f) = \x -> g (f x) > >then (.) is the currying of composition: > > (.) = curry composition > >or > > (.) g f = \x -> g (f x) > >-Jeff > > >On 9/21/07, PR Stanley <prstanley(a)ntlworld.com> wrote: > > Hi > > (.) :: (b -> c) -> (a -> b) -> (a -> c) > > While I understand the purpose and the semantics of the (.) operator > > I'm not sure about the above definition. > > Is the definition interpreted sequentially - (.) is a fun taht takes > > a fun of type (b -> c) and returns another fun of type (a -> b) etc? > > Any ideas? > > Thanks, Paul > > > > _______________________________________________ > > Haskell-Cafe mailing list > > Haskell-Cafe(a)haskell.org > > http://www.haskell.org/mailman/listinfo/haskell-cafe > >

6 8

Re: [Haskell-cafe] Re: Very crazy
by Andrew Coppin 26 Sep '07

26 Sep '07

Chaddaï Fouché wrote: > 2007/9/25, Andrew Coppin <andrewcoppin(a)btinternet.com>: > > >> I just found it rather surprising. Every time *I* try to compose with >> functions of more than 1 argument, the type checker complains. >> > > There is no function that takes more than one argument in Haskell. ;-) > map _could_ be seen as a function with 2 arguments, but in this case > it's more useful to think of it as a function that take one argument > f, a function that turn 'a into 'b and turn it into a new function > that turn a list of 'a into a list of 'b. > This is why I found it so surprising - and annoying - that you can't use a 2-argument function in a point-free expression. For example, "zipWith (*)" expects two arguments, and yet sum . zipWith (*) fails to type-check. You just instead write \xs ys -> sum $ zipWith(*) xs ys which works as expected. I can't figure out why map . map works, but sum . zipWith (*) doesn't work. As I say, the only reason I can see is that the type checker hates me and wants to force me to write everything the long way round...

5 4