March 2012 - Haskell-Cafe

Re: [Haskell-cafe] using mutable data structures in pure functions
by Ryan Ingram 14 Mar '12

14 Mar '12

On Sun, Mar 11, 2012 at 8:38 PM, E R <pc88mxer(a)gmail.com> wrote: > A pure function can allocate and modify memory as long as a) it never > returns a reference to the memory or b) it never again modifies the > memory once it returns (i.e. it returns an immutable object). > That's a reasonable first approximation to the problem, yes. It gets a bit more complicated due to laziness (what if the mutation gets delayed until some later part of the output is examined?) So, again, what is the Haskell philosophy towards using mutable data > structures in pure functions? Is it: > > 1. leave it to the compiler to find these kinds of opportunities > 2. just use the immutable data structures - after all they are just as > good (at least asymptotically) > 3. you don't want to use mutable data structures because of _____ > 4. it does happen, and some examples are ______ > There are two ways in which Haskell encourages the use of mutable data structures in a pure way. The first is in the inherent mutation caused by laziness. For example: type Positive = Integer -- trie of binary representation of positive number -- [1] -> tOne -- x ++ [0] -> lookup x . tEven -- x ++ [1] -> lookup x . tOdd data Trie a = Trie { tOne :: a, tEven :: NatTrie a, tOdd :: NatTrie a } lookupTrie :: Trie a -> Positive -> a lookupTrie t 1 = tOne t lookupTrie t n | even n = lookupTrie (tEven t) (n `div` 2) | otherwise = lookupTrie (tOdd t) (n `div` 2) -- div drops remainder makeTrie :: (Positive -> a) -> Trie a makeTrie f = Trie (f 1) e o where e = makeTrie $ \n -> f (2*n) o = makeTrie $ \n -> f (2*n + 1) memoize :: (Positive -> a) -> (Positive -> a) memoize = lookupTrie . makeTrie collatz_rec :: (Positive -> Integer) -> Positive -> Integer collatz_rec f 1 = 0 collatz_rec f n | even n = 1 + f (n `div` 2) | otherwise = 1 + f (3*n + 1) collatz = memoize (collatz_rec collatz) In this case, makeTrie creates a thunk, and it's only evaluated where requested by lookupTrie. You can call collatz at many different values and later calls will be much faster, as the mutation caused by lazy evaluation 'remembers' the values. The second is by explicitly documenting that you are using a temporarily mutable structure, which is the ST monad: instance Monad (ST s) newSTRef :: a -> ST s (STRef s a) readSTRef :: STRef s a -> ST s a writeSTRef :: STRef s a -> a -> ST s () -- and similar interface for mutable STArrays runST :: (forall s. ST s a) -> a -- note higher rank type A computation in the ST monad is an impure computation that can modify memory, but only memory allocated within that same computation. The higher rank type in runST makes it safe to do so--references from one ST computation cannot escape to any other ST computation. So even though internally some pure value might rely on an impure computation, it's safe to do so in a pure context. Here's a sample implementation of ST: -- DO NOT EXPORT THESE CONSTRUCTORS newtype ST s a = ST (IO a) newtype STRef s a = STRef { getRef :: IORef a } runST :: (forall s. ST s a) -> a runST (ST act) = unsafePerformIO act -- Actually safe! newSTRef :: a -> ST s (STRef s a) newSTRef a = ST $ liftM STRef (newIORef a) readSTRef :: STRef s a -> ST s a readSTRef (STRef r) = ST $ readIORef r writeSTRef :: STRef s a -> a -> ST s () writeSTRef (STRef r) a = ST $ writeIORef r a There's some usage examples at http://www.haskell.org/haskellwiki/Monad/ST -- ryan

1 0

Polymorphic addition function with variable number of arguments?
by Some One 13 Mar '12

13 Mar '12

Dear Haskellers, I'm trying to define a polymorphic "add" function which takes a variable number of arguments (instance of Num) and returns their sum. I don't want to specify the types of the arguments while calling the function, I just want to , at most, specify the return type (*it should infer that the return type is the type of the arguments*). class Add a b where add :: a -> b instance Num a => Add a a where add = id instance (Num a, Add a b) => Add (a -> b) where add x y = add (x + y) Can someone tell me why this is not working and propose a fix for this, if possible? Thanks in advance

2 3

Inecxact map?
by Morten Olsen Lysgaard 13 Mar '12

13 Mar '12

I'm running a project where i want to generate a map of a rather large data collection. The map is if the form: Data.Map.Map String a I'd like to be able to do inexact lookups on the map. Firstly, ignore the difference between upper lower case, that's easy. But secondly, have a function: search :: (Num b) => Data.Map.Map String a -> String -> b -> [a] This function is like the normal lookup, but it takes an extra argument b. B is the allowed character error rate. That is the Levenstein distance divided on the length. It should return all the strings that has an error rate lower that b and in a ordered manner, best first. Is it possible to design such a datastructure efficiently? Does there already exist something like this? If not, where would i begin to create this? Any advices or knowledge appreciated. -- Morten

3 2

cabal test-suite library recompilation
by Ozgur Akgun 13 Mar '12

13 Mar '12

Hi all, I've recently started to move my tests to use the new cabal test-suite framework. Old setup: The cabal file compiles one library + a few executables. The library contains almost all of the code and exposes the necessary modules for use by the executables. The executables mainly consist of one main file. This way, the library is only compiled once and used multiple times by the executables. Great. One of the executables compile a test runner, and is handled similarly. New setup, using test-suite: I've deleted the executable section for the test runner and added a test-suite section instead. To my surprise, the library is compiled twice now. Hence, it takes twice as long. And it is a clear regression compared to my old setup. While waiting for a build to finish [ :) ], I just wanted to write an email and check if this is intentional or only an oversight. Or maybe a technical limitation for the time being? Thanks, Ozgur

2 2

ANNOUNCE: join (UHac <$> DHD)
by Sean Leather 13 Mar '12

13 Mar '12

You can still join us at the DHD >>= UHac, but the time is running out. http://www.haskell.org/haskellwiki/DHD_UHac Deadline: April 1 (no fooling!) We've also have a few updates: * We put the DHD program up, at least as much of it as we have. http://www.haskell.org/haskellwiki/DHD_UHac/DHD_Program * As you can see from the program, there is still room for more speakers. In particular, we'd like to hear from people coming outside Utrecht and the Netherlands. We'd also like to see more lightning talks. Send Sean an email with your idea: leather(a)cs.uu.nl * UHac on Friday has moved to a "new" location. Actually, it's the same location as on Saturday and Sunday, so that should make things easier. See you in Utrecht! The Organizers: Sean Leather Jurriën Stutterheim Jurriaan Hage P.S. Make sure your Monad is also a Functor. P.P.S. Apologies for multiple copies.

1 0

Re: [Haskell-cafe] Empty Input list
by Kevin Clees 13 Mar '12

13 Mar '12

Hey Chris, thank you for your help! Your last comment with the (!!)-thing was a very good idea! Now my function looks like this: tmp:: [(Int, Int)] -> Int -> (Int, Int) tmp [] y = (0,0) tmp xs y = xs !! (y-1) If the function returns (0,0) it will blocked by another function. If I want to use the "maybe" return, I get some new trouble that I don't like - so I chose that way :) Thank you again Kevin

5 4

Leksah Install Issue (cabal experts please help)
by Hamish Mackenzie 13 Mar '12

13 Mar '12

pozic raised an install issue on IRC. Basically he was getting... ~$ cabal install leksah-server Resolving dependencies... cabal: Couldn't read cabal file "leksah-server/0.12.0.3/leksah-server.cabal" To reproduce this issue. Use GHC 6.12.3, 7.0.3 or 7.2.2 to "cabal install cabal-install" then run "cabal install leksah-server". To work around it install GHC 7.0.4 or 7.4.1 and use it to run "cabal install cabal-install" (then you can go back to the old GHC if you want). Cabal experts, is there a better work around than this? The current leksah-server.cabal requires Cabal 1.10.2 or greater because it has a "test-suite" section for "cabal test". This is fine if you have installed cabal-install with GHC 7.0.4 or 7.4.1, but if you install cabal-install with older versions of GHC (including 7.2.2) then it can't handle the file format. I could upload a new leksah-server to hackage (with the unit tests removed), but that would not stop cabal-install from failing to read leksah-server 0.12.0.3 and bombing out (there is already a 0.12.0.4 and it is not getting to that one). Even if you "cabal unpack" and then modify the .cabal file and run "cabal install" it still fails with the same error. If you can think of a better solution than asking users to install GHC 7.0.4 or 7.4.1 to build cabal-install, then please let me know.

2 7

Empty Input list
by Kevin Clees 12 Mar '12

12 Mar '12

Dear Haskell friends, what can I do, if a function gets an empty input list? I want, that it only returns nothing. This is my source code: tmp:: [(Int, Int)] -> Int -> (Int, Int) tmp (x:xs) y | y == 1 = x | y > 1 = tmp xs (y-1) If this function gets an empty list, he throws "Exception: sortAlgo.hs:(18,1)-(21,44): Non-exhaustive patterns in function Main.tmp" *Main> tmp [(1,2),(3,2)] 1 (1,2) *Main> tmp [(1,2),(3,2)] 2 (3,2) *Main> tmp [] 1 *** Exception: sortAlgo.hs:(20,1)-(22,44): Non-exhaustive patterns in function Main.listElementIntInt Thank you for any help ! Best regards Kevin

2 2

Re: [Haskell-cafe] IO() and other datatypes
by Kevin Clees 12 Mar '12

12 Mar '12

Great, Thank you !

1 0

Helper classes for Generics
by Reiner Pope 12 Mar '12

12 Mar '12

Hi all, I've been playing with GHC's new generics features (see http://www.haskell.org/ghc/docs/latest/html/users_guide/generic-programming…) All the documentation I've seen suggests creating a "helper class" -- for instance, the GSerialize class in the above link -- on which one defines generic instances. It seems to me that this isn't necessary. For example, here's the the example from the GHC docs, but without a helper class: > -- set the phantom type of Rep to (), to avoid ambiguity > from0 :: Generic a => a -> Rep a () > from0 = from > > data Bit = O | I > > class Serialize a where > put :: a -> [Bit] > > default put :: (Generic a, Serialize (Rep a ())) => a -> [Bit] > put = put . from0 > > instance Serialize (U1 x) where > put U1 = [] > > instance (Serialize (a x), Serialize (b x)) => Serialize ((a :*: b) x) where > put (x :*: y) = put x ++ put y > > instance (Serialize (a x), Serialize (b x)) => Serialize ((a :+: b) x) where > put (L1 x) = O : put x > put (R1 x) = I : put x > > instance (Serialize (a x)) => Serialize (M1 i c a x) where > put (M1 x) = put x > > instance (Serialize a) => Serialize (K1 i a x) where > put (K1 x) = put x Is there a reason to prefer using helper classes? Or perhaps we should update the wiki page (http://www.haskell.org/haskellwiki/Generics) to avoid using helper classes? Regards, Reiner

3 5