August 2010 - Beginners

randomize the order of a list
by Gabriel Scherer 17 Sep '10

17 Sep '10

Gaius Hammond wrote: > I am trying to randomly reorder a list (e.g. shuffle a deck of cards) . > My initial approach is to treat it as an array, generate a list of > unique random numbers between 0 and n - 1, then use those numbers as new > indexes. Felipe Lessa wrote: > Note: you could use random-shuffle package [1]. > > [1] http://hackage.haskell.org/package/random-shuffle Heinrich Apfelmus wrote: > For another approach, see also > > http://apfelmus.nfshost.com/articles/random-permutations.html Thanks for the link apfelmus, it's fairly interesting. The key to making it work is the weighting of lists during merging based on their lengths. I wonder if other sort algorithm can be adapted in such a way, while preserving uniformity. Quicksort for example : is it enough to choose the result position of the pivot randomly, and then placing elements on either side with a probability of 1/2 ? There is another sort-based approach that is probably less elegant, but simpler in the sense that you don't have to rewrite your sorting routines : pick random "weights" for each of your elements, and sort the list based on the weights. This approach has been studied and criticized by [Oleg], whose analysis is the base of the random-shuffle package. Oleg rightly points out that this method does not achieve uniformity in general. What he failed to notice is that there is a simple workaround to regain uniformity with minimal changes. [Oleg] http://okmij.org/ftp/Haskell/perfect-shuffle.txt The uniformity breaker is the case were two elements get equal weights. In his example, weights for a 2-size lists are choosed in {0, 1}. In the two corner case were both elements get picked the same weight, the sorting routine make an arbitrary choice : for example, if it is stable, it will put first the element occuring sooner in the list. This arbitrary choice breaks uniformity. The workaround is simple : pick weights that are all differents. If the weights are picked among [1, n] were n is the size of the list, it is difficult and inneficient to generate a list of unique random numbers. But you can choose weights in arbitrary intervals. The bigger it is, the smaller the chance you have to pick weights again becomes (though due to the birthday paradox, it does not decrease that fast). To sum it up, here is the algorithm to shuffle a list : - for each element in the list, pick a random list - pick another weight list while two equal weights were picked - once you've picked *unique* weights, shuffle the elements of the list by comparing their weights If the weight are taken in a big enough interval (say [1, 2^64]), the average number of repicks necessary is small enough for this algorithm to be just a sorting using your preferred algorithm. I haven't went through the trouble of computing the necessary interval bound to get a small enough chance of conflict, but I believe the forth power of the size of the list should be enough. An even better technique is to use lazy lists of {0, 1} (representing real numbers) as weights, with each list element lazily randomly computed. You are sure than no two such lists are equal (they're different with probability 1). This amounts to a dynamical random refining of weights during the sorting : "two of my real number weights are equal at granularity 2^-N ? Let's make a random choice so that their {N-1}th digit is different !"

4 9

Mixing IO and other monads
by Brian Victor 08 Sep '10

08 Sep '10

I've managed to create the sort of nested case code that all the monad tutorials warn you against. I haven't found a way to work myself out of it, though. If I've understood monad transformers conceptually, this seems like the sort of thing they'd be good for, but I don't know how to actually make what I need. Here's the code I have. getDefaultInputDeviceID and getDefaultOutputDeviceID are from PortMidi, and return IO (Maybe Int). openInput and openOutput return IO (Either PMStream PMError). At this point, I'd be happy to get the second half of the function refactored into monads. main :: IO () main = do initialize ideviceId <- getDefaultInputDeviceID case ideviceId of Nothing -> putStrLn "No default input device" Just inputDeviceId -> do odeviceId <- getDefaultOutputDeviceID case odeviceId of Nothing -> putStrLn "No default output device" Just outputDeviceId -> do openInputResult <- openInput inputDeviceId case openInputResult of Right err -> putStrLn $ show err Left inputStream -> do openOutputResult <- openOutput outputDeviceId 0 case openOutputResult of Right err -> putStrLn $ show err Left outputStream -> runTranslationLoop inputStream outputStream It seems like I ought to be able to change the second half of the function to something like this: openStreamsAndLoop :: (Num a) => a -> a -> IO (Maybe err) openStreamsAndLoop inputDeviceId outputDeviceId = do inputStream <- openInput inputDeviceId outputStream <- openOutput outputDeviceId 0 runTranslationLoop inputStream outputStream return Nothing But how do I create an IO (Maybe err) monad? -- Brian

4 5

confusion about parameterized types.
by Michael Litchard 31 Aug '10

31 Aug '10

Here is a record I defined > module PrepData where > data Value = Cost Int | ID Int > type Tname = String > data StudentsOrActivites = Students String | Activities String > data Table soa v = PopTable > { tableName :: Tname > , tableColumns :: [(soa, v)] > } deriving (Show, Read) I'm trying to define another record in terms of Table > data ProcessData = > ProcessData { flatfile :: String > , processfunc :: String -> what I would like processfunc to be is a function that takes a String and returns a Table. The type variables are tripping me up. Could someone help me work out the syntax, and the clarifying of my intent?

3 5

Results of Bug Report
by David Webster 29 Aug '10

29 Aug '10

I submitted a bug report to Haskell-Platform a few days ago. The ticket was assigned an owner who accepted it. How will I know if the problem has been corrected? David Webster

2 1

instances of different kinds
by Greg 29 Aug '10

29 Aug '10

Hi-- More silly typeclass questions. I'm not sure the right way to ask it, so I'll start with a failed code snippet: data Foo a = Foo a class TwoPi a where div2pi :: (Floating b) => a -> b instance (Floating a) => TwoPi (Foo a) where div2pi (Foo a) = a / (2*pi) instance TwoPi Float where div2pi a = a / (2*pi) This code is obviously meaningless, but I'm trying to figure out how you can create instances of a typeclass for data types of different kinds. I have a similar piece of code that works: data Foo a = Foo a class Testable a where isPos :: a -> Bool instance (Ord b, Num b) => Testable (Foo b) where isPos (Foo b) = b > 0 instance Testable Float where isPos a = a > 0 One obvious difference is that the type of isPos is a -> Bool, with a defined type as the return. I'd rather not commit to a specific Floating type up front (I'd prefer sometimes Float sometimes Double, depending on the 'a' in Foo a, but trying to declare it as Float doesn't help me. This fails: data Foo a = Foo a class TwoPi a where div2pi :: a -> Float instance (Floating b) => TwoPi (Foo b) where div2pi (Foo b) = b / (2*pi) instance TwoPi Float where div2pi a = a / (2*pi) The errors I'm getting are various permutations of: Couldn't match expected type `Float' against inferred type `b' `b' is a rigid type variable bound by the instance declaration at gcbTestBad.hs:8:19 In the expression: b / (2 * pi) In the definition of `div2pi': div2pi (Foo b) = b / (2 * pi) In the instance declaration for `TwoPi (Foo b)' What is the difference between these last two cases ("a -> Bool" and "a -> Float"), and is there anyway to make "a -> b" work? Thanks-- Greg

3 8

Changing evalList to parList creates a space leak?
by Travis Erdman 29 Aug '10

29 Aug '10

Ok, since I last visited, as a result of the help from contributors on this list, I've reached a nice spot. The serial implementation of my processing algorithm works quite quickly (including the tree pruning that I mentioned last time) and the space leaks have been eliminated without resort to the dreadful foldl'rnf. Here are simplified versions of key components of my program: data Tree a = Node a [Tree a] calcTree :: Tree MyData -> InputData -> Tree MyData calcTree (Node cargo subtrees) input = Node (process cargo input) recurseChildren where process a b = .... recurseChildren = map (\t -> calcTree t input) subtrees `using` evalList rseq newTree = foldl' calcTree starttree (take n inputdatalist) The <`using` evalList rseq> term at the end of recurseChildren was key to solving a space leak without resorting to foldl'rnf (which is a performance killer). This is also the place in my code where it makes the most sense to introduce some parallelism (ie to traverse the subtrees in parallel). However, when I simply change the evalList to a parList, a space leak is created anew, which I didn't anticipate at all. (of course, I also made the change of compiling with -threaded and -feager-blackholing flags ... but if I compile with those flags and leave it as evalList, there is no space leak). I'm using parallel-3.1.0.0, so it's not the space leak from parallel-1.1.x. Any ideas why this simple change should introduce a space leak? How might I get to where I want to go? thanks again, Travis

1 0

randomize the order of a list
by A Smith 29 Aug '10

29 Aug '10

I've abeen recommended on good authority(my son, a Cambridge Pure maths graduate, and Perl/Haskell expert) , and backed by a Google search that Fisher-Yates shuffle is the one to use, as it produces total unbiased results with every combination equally possible. As with most things with computers,don't reinvent the eheel, it's almost certainly been done before by someone brighter that you, Fisher,Yates. & Knuth! -- Andrew Smith B.Sc(Hons),MBA Edinburgh,Scotland On 27 August 2010 21:02, Gaius Hammond <gaius(a)gaius.org.uk> wrote: > Hi all, > > > > I am trying to randomly reorder a list (e.g. shuffle a deck of cards) . My > initial approach is to treat it as an array, generate a list of unique > random numbers between 0 and n - 1, then use those numbers as new indexes. I > am using a function to generate random numbers in the State monad as > follows: > > > > randInt∷ Int → State StdGen Int > randInt x = do g ← get > (v,g') ← return $ randomR (0, x) g > put g' > return v > > > > This is pretty much straight from the documentation. My function for the > new indexes is: > > > > -- return a list of numbers 0 to x-1 in random order > randIndex∷ Int → StdGen → ([Int], StdGen) > randIndex x = runState $ do > let randIndex' acc r > | (length acc ≡ x) = acc > | (r `elem` acc) ∨ (r ≡ (−1)) = do > r' ← randInt (x − 1) > randIndex' acc r' > | otherwise = do > r' ← randInt (x − 1) > randIndex' r:acc r' > in > randIndex' [] (−1) > > > > This fails to compile on > > > > > Couldn't match expected type `[a]' > against inferred type `State StdGen b' > In a stmt of a 'do' expression: r' <- randInt (x - 1) > In the expression: > do { r' <- randInt (x - 1); > randIndex' acc r' } > > > > > I can see what's happening here - it's treating randIndex' as the second > argument to randInt instead of invisibly putting the State in there. Or am I > going about this completely the wrong way? > > > Thanks, > > > > G > > > > > _______________________________________________ > Beginners mailing list > Beginners(a)haskell.org > http://www.haskell.org/mailman/listinfo/beginners >

3 2

randomize the order of a list
by Gaius Hammond 28 Aug '10

28 Aug '10

Hi all, I am trying to randomly reorder a list (e.g. shuffle a deck of cards) . My initial approach is to treat it as an array, generate a list of unique random numbers between 0 and n - 1, then use those numbers as new indexes. I am using a function to generate random numbers in the State monad as follows: randInt∷ Int → State StdGen Int randInt x = do g ← get (v,g') ← return $ randomR (0, x) g put g' return v This is pretty much straight from the documentation. My function for the new indexes is: -- return a list of numbers 0 to x-1 in random order randIndex∷ Int → StdGen → ([Int], StdGen) randIndex x = runState $ do let randIndex' acc r | (length acc ≡ x) = acc | (r `elem` acc) ∨ (r ≡ (−1)) = do r' ← randInt (x − 1) randIndex' acc r' | otherwise = do r' ← randInt (x − 1) randIndex' r:acc r' in randIndex' [] (−1) This fails to compile on Couldn't match expected type `[a]' against inferred type `State StdGen b' In a stmt of a 'do' expression: r' <- randInt (x - 1) In the expression: do { r' <- randInt (x - 1); randIndex' acc r' } I can see what's happening here - it's treating randIndex' as the second argument to randInt instead of invisibly putting the State in there. Or am I going about this completely the wrong way? Thanks, G

4 4

Fwd: [Haskell-beginners] instances of different kinds
by Tobias Brandt 27 Aug '10

27 Aug '10

Forgot to reply to the list, sorry. ---------- Forwarded message ---------- From: Tobias Brandt <tob.brandt(a)googlemail.com> Date: 27 August 2010 11:14 Subject: Re: [Haskell-beginners] instances of different kinds To: Greg <greglists(a)me.com> On 27 August 2010 10:58, Greg <greglists(a)me.com> wrote: > data Foo a = Foo a > > class TwoPi a where > div2pi :: (Floating b) => a -> b > div2pi is polymorphic in a AND b. They are completely independent. > instance (Floating a) => TwoPi (Foo a) where > div2pi (Foo a) = a / (2*pi) > but here, div2pi has type Floating a => Foo a -> a. > > data Foo a = Foo a > > class TwoPi a where > div2pi :: a -> Float > > instance (Floating b) => TwoPi (Foo b) where > div2pi (Foo b) = b / (2*pi) > now div2pi has type Floating a :: Foo a -> a, but should have Floating a :: Foo a -> Float There are two possible solutions (I can think of). 1. make div2pi less polymorphic: class TwoPi a where div2pi :: a -> a then your first instance works 2. use associated types: class TwoPi a where type TwoPiRes a div2pi :: a -> TwoPiRes a instance Floating a => TwoPi (Foo a) where type TwoPiRes (Foo a) = a div2pi (Foo a) = a /(2*pi)

1 0

Encapsulation and Polymorphism
by Drew Haven 27 Aug '10

27 Aug '10

I thought I was getting pretty good at Haskell, until I ran into this problem. It's basically a way of maintaining encapsulation of data and functions while being able to have a container, such as a list, hold these items without worrying about their differences. In OO this would be pretty easy. You'd have an interface of some sort and the container would hold objects of the interface type. Then you could write the individual classes that implement that interface in their own files and the main program wouldn't have to know about the details. I'm trying to write a silly little life simulator. We've got a world where many different entities exist. These entities are all different, but for a start we'll use fish and shark. The fish like to swim around in the sea, and will manage to eat some amount of the overall food supply. The amount they consume from year to year varies and they have to consume a minimum amount every year or they die. When they've eaten enough food and have build up a surplus, they'll reproduce, but if they're starving they can't. Sharks are similar, except their food supply is the fish. The two are very similar, but do slightly different things. And every fish or shark has to keep track of its own amount of consumed food. If I wanted to define these separately, the best I've come up with is to create a data type that has all the information necessary, then somewhere maintain a master algebraic data type which wraps each of these in a type constructor. I can then write another head for a general function that will match that type constructor and describe the behavior. I tried something clever with closures, but it turned out to be too clever for me and I couldn't avoid infinite types. Thoughts? Drew Haven drew.haven(a)gmail.com

5 8