October 2009 - Haskell-Cafe

Sharing Subexpressions: Memoization of Fibonacci sequence
by SimonK77 14 Oct '09

14 Oct '09

Hallo everyone, the last few weeks I was trying to get used to memoization in haskell. As I found out in a previous post, memoization in haskell is, due to the graph reduction strategy used in haskell, almost always implemented by sharing subexpressions in an expression. In examples as the following this is quite easy to see. fibs = 0:1:zipWith (+) fibs (tail fibs) But as I browsed through the search results from google for this topic, I encountered the following implementation: memoized_fib :: Int -> Integer memoized_fib = let fib 0 = 0 fib 1 = 1 fib n = memoized_fib (n-2) + memoized_fib (n-1) in (map fib [0 ..] !!) You'll find it at Haskell.org. Here's the http://www.haskell.org/haskellwiki/Memoization link Let's assume we have the following implementation of the higher-order-function map: map :: (a -> b) -> [a] -> [b] map _ [] = [] map f (x:xs) = f x : map f xs The reduction sequence of memoized_fib 5 would start as follows: //Reduction of memoized_fib 5 memoized_fib 5 = (map fib [0..] !!) 5 = (fib 0 : map fib [1..] !!) 5 = (0 : fib 1 : map fib [2..] !!) 5 = (0 : 1 : fib 2 : map fib [3..] !!) 5 = (0 : 1 : (memoized_fib 0 + memoized_fib 1) : fib 3 : map fib [4..] !!) 5 = (0 : 1 : (map fib [0..] !! 0 + map fib [0..] !! 1) : (memoized_fib 1 + memoized_fib 2) : map fib [4..] !!) 5 . . . . and so on! I can't see where the sharing of subexpressions happens here. Any help is highly appreciated. Best regards Simon -- View this message in context: http://www.nabble.com/Sharing-Subexpressions%3A-Memoization-of-Fibonacci-se… Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

4 6

Setting environment variables on Windows
by Sönke Hahn 14 Oct '09

14 Oct '09

Hi! I need to set an environment variable from Haskell and i would like to do that cross-platform. There is System.Posix.Env.setEnv, which does exactly, what i want on Linux. There is the module System.Environment, which seems to be cross-platform, but it does not contain functions to manipulate the environment (, just to inspect it). At first glance, I didn't find anything relevant in the sub-modules of System.Win32. Is this just not implemented? How could i implement it myself? Grateful for any comment, Sönke

3 5

Why does replicateM (10^6) $ return 0 produce output in the IO monad, but overflow the maybe monad?
by Thomas Hartman 14 Oct '09

14 Oct '09

-- Why does replicateM (10^6) $ return 0 produce output in the IO monad, but overflow the maybe monad? iterateNTimes i f x = foldr (.) id (replicate i f) $ x tntIO :: IO Int -- same as replicateM (10^6) $ return 0, same as sequence . replicate (10^6) $ return 0 tntIO = return . head =<< (iterateNTimes (10^6) (mcons . return $ 0) (return [])) -- produces output tntMb :: Maybe Int -- overflows tntMb = return . head =<< (iterateNTimes (10^6) (mcons . return $ 0) (return [])) -- stack overflow -- equivalently: mcons m ms = (:) <$> m <*> ms mcons m ms = ap (liftM (:) m) $ ms I guess the maybe version builds up a huge chain of unevaluated thunks somewhere, that's usually the reason. But specifically where and why, and why doesn't IO do the same thing? Equivalent, with 3 element list: (mcons $ return $ 0 ) $ (mcons $ return $ 0) $ (mcons $ return $ 0) $ (return []) (ap . liftM (:) . return $ 0 ) $ (ap . liftM (:) . return $ 0) $ (ap . liftM (:) . return $ 0) $ (return []) (ap $ liftM (:) $ return $ 0 ) $ (ap $ liftM (:) $ return $ 0) $ (ap $ liftM (:) $ return $ 0) $ (return []) t.

1 0

example of PortMidi use
by Michael Mossey 14 Oct '09

14 Oct '09

Can someone give me an example of Sound.PortMidi use? I'm having trouble. This program has bugs---makes sound only intermittently, and seems to have set up some kind of loop that is sending midi messages continuously even after terminating the program: import Sound.PortMidi import Foreign.C msgs = [ (0::CULong,PMMsg 0x9c 0x40 0x40) , (500, PMMsg 0x8c 0x40 0x40) , (1000, PMMsg 0x9c 0x41 0x40) , (1500, PMMsg 0x8c 0x41 0x40) ] main = do let deviceId = 12 initialize >>= print getDeviceInfo deviceId >>= print startTime <- time let evts = map (\(t,msg) -> PMEvent msg (t+startTime)) msgs result <- openOutput deviceId 10 case result of Right err -> putStrLn ("After open: " ++ show err) Left stream -> do result <- writeEvents stream evts putStrLn ("After write: " ++ show result) close stream return () terminate >>= print

2 1

(no subject)
by oleg＠okmij.org 14 Oct '09

14 Oct '09

Martin Sulzmann wrote: > "Undecidable" instances means that there exists a program for which there's > an infinite reduction sequence. I believe this may be too strong of a statement. There exists patently terminating type families that still require undecidable instances in GHC. Here is an example: > {-# LANGUAGE TypeFamilies #-} > > type family I x :: * > type instance I x = x > > type family B x :: * > type instance B x = I x GHC 6.8.3 complaints: Application is no smaller than the instance head in the type family application: I x (Use -fallow-undecidable-instances to permit this) In the type synonym instance declaration for `B' But there cannot possibly be any diverging reduction sequence here, can it? The type family I is the identity, and the type family B is its alias. There is no recursion. The fact that type families are open is not relevant here: our type families I and B are effectively closed, because one cannot define any more instance for I and B (or risk overlap, which is rightfully not supported for type families). The reason GHC complains is because it checks termination instance-by-instance. To see the termination in the above program, one should consider instances I and B together. Then we will see that I does not refer to B, so there are no loops. But this global termination check -- for a set of instances -- is beyond the abilities of GHC. This is arguably the right decision: after all, GHCi is not a full-blown theorem prover. Thus there are perfectly decidable type programs that require undecidable instances. Indeed, there is no reason to be afraid of that extension.

2 1

Reverse dependencies in Hackage
by haskell＠kudling.de 14 Oct '09

14 Oct '09

Nice, thank you for the great work. Browsing the reverse dependencies of popular packages like "bytestring" http://bifunctor.homelinux.net/~roel/cgi-bin/hackage-scripts/revdeps/bytest… can be improved a bit. 1) Can you please sort the reverse dependent package names? That makes it easier to find packages with certain names. 2) I found the columns "Direct" and "Indirect" confusing until i found out that they show the number of reverse dependencies for those packages themselves and are not related to direct/indirect dependencies of the current package. I don't think it is necessary to provide those data here and i would be in favor of reducing the information overload by leaving those data to each package detail page. 3) Can you try to print the reverse packages horizontally instead of vertically in tables? Browsing two long tables of direct/indirect reverse dpependencies like for "bytestring" makes it tedious to get an overview. Besides that, i am quite happy. Thanks, Lenny

2 1

Exponential complexity of type checking (Was: Type-level naturals & multiplication)
by Brad Larsen 14 Oct '09

14 Oct '09

On Tue, Oct 13, 2009 at 3:37 AM, Simon Peyton-Jones <simonpj(a)microsoft.com> wrote: > | > Is there any way to define type-level multiplication without requiring > | > undecidable instances? > | > | No, not at the moment. The reasons are explained in the paper "Type > | Checking with Open Type Functions" (ICFP'08): > | > | http://www.cse.unsw.edu.au/~chak/papers/tc-tfs.pdf > | > | We want to eventually add closed *type families* to the system (ie, > | families where you can't add new instances in other modules). For > | such closed families, we should be able to admit more complex > | instances without requiring undecidable instances. > > It's also worth noting that while "undecidable" instances sound scary, but all it means is that the type checker can't prove that type inference will terminate. We accept this lack-of-guarantee for the programs we *run*, and type inference can (worst case) take exponential time which is not so different from failing to terminate; so risking non-termination in type inference is arguably not so bad. > > Simon > I have written code that makes heavy use of multi-parameter type classes in the ``finally tagless'' tradition, which takes several seconds and many megabytes of memory for GHCI to infer its type. However, that example is rather complicated, and I am not sure its type inference complexity is exponential---it is at least very bad. Are there any simple, well-known examples where Haskell type inference has exponential complexity? Or Hindley-Milner type inference, for that matter? (Haskell 98 is not quite Hindley-Milner?) Sincerely, Brad Larsen

5 8

ANN: fp-southwales, the South Wales Functional Programming User Group
by Andy Gimblett 14 Oct '09

14 Oct '09

Dear friends, It is my pleasure to announce the formation of fp-southwales, a user group for anybody interested in functional programming in the area of south Wales, UK. We're based out of Swansea University's Computer Science department, where there are a few of us using Haskell for our research, but we welcome anyone who wants to join in, from academia or industry, from Swansea, or Cardiff, or indeed anywhere in south Wales. As the name of the group also suggests, we're interested in all aspects of functional programming, not just Haskell, although we expect that to be a central topic, for now at least. We exist online as a google group: http://groups.google.com/group/fp-southwales The first point of business is: hello, what shall we do, and when shall we do it? :-) http://groups.google.com/group/fp-southwales/browse_thread/thread/ddb2d352a… All welcome! -Andy

1 0

why does "iterateNTimes (10^6) (ap . liftM (:) . return $ 0) (return [])" produce output in the IO monad, but stack overflow in the maybe monad?
by Thomas Hartman 13 Oct '09

13 Oct '09

Can someone explain why the one stack overflows and the other one doesn't? iterateNTimes i f x = foldr (.) id (replicate i f) $ x tntIO :: IO Int -- same as replicateM (10^6) $ return 0 , and same as sequence . replicate (10^6) $ return 0 tntIO = iterateNTimes (10^6) (ap . liftM (:) . return $ ) (return []) -- produces output tntMb :: Maybe Int -- overflows tntMb = iterateNTimes (10^6) (ap . liftM (:) . return $ ) (return []) -- stack overflow

1 1

Type-level naturals & multiplication
by Brad Larsen 13 Oct '09

13 Oct '09

Suppose we implement type-level naturals as so: data Zero data Succ a Then, we can reflect the type-level naturals into a GADT as so (not sure if ``reflect'' is the right terminology here): data Nat :: * -> * where Zero :: Nat Zero Succ :: Nat a -> Nat (Succ a) Using type families, we can then proceed to define type-level addition: type family Add a b :: * type instance Add Zero b = b type instance Add (Succ a) b = Succ (Add a b) Is there any way to define type-level multiplication without requiring undecidable instances? Sincerely, Brad

5 6