5
\$\begingroup\$

I've been learning Haskell for a few weeks after coming from a C# background. I've written a function to return a number of unique Ints from a specified range:

module MrKWatkins.Random (
    uniqueRandomInts
) where

import System.Random
import qualified Data.IntSet as I

uniqueRandomInts :: RandomGen g => (Int, Int) -> Int -> g -> ([Int], g)
uniqueRandomInts range@(min, max) n rng
    | n < 0             = error "n must be positive"
    | n > max - min + 1 = error "n is too large for range"
    | otherwise         = recursion n I.empty ([], rng)
    where 
        recursion n used (xs, rng)
            | n == 0          = (xs, rng)
            | I.member x used = recursion n used (xs, rng')
            | otherwise       = recursion (n-1) (I.insert x used) (x:xs, rng')
            where 
                (x, rng') = randomR range rng

Then to produce 5 numbers in the (inclusive) range 1 -> 10 the call would be something like:

uniqueRandomInts (1, 10) 5 $ mkStdGen 42

Firstly I have a few specific questions:

  1. I've prefixed my module name with MrKWatkins to distinguish it as my module (much as I would with a namespace in C#). Is this common practice, or would I be better with a single word for the module name that is more descriptive?
  2. I've done some pre-condition checking on the parameters, throwing exceptions if they're not satisfied. Is this common practice in Haskell, and is this the best way to do it?
  3. I've used a nested function for the recursion. Would I be better off separating this out into a top level function that I don't export from the module?
  4. I've reused some variable names in the recursion function, hiding the ones from the parent scope. Should I use different names instead?

On top of those if there is any advice on style, better ways to implement the above or just general advice would be greatly appreciated.

\$\endgroup\$
  • 2
    \$\begingroup\$ obligatory xkcd.com/221 \$\endgroup\$ – Max Dec 5 '13 at 7:49
  • \$\begingroup\$ On point (2): Often, Haskell code (esp public APIs) will constrain the type of the parameter into an acceptable range; that way, it is impossible to construct an invalid argument. If it can't be done with the type system (so that erroneous input produces a static error), we turn to smart constructors. \$\endgroup\$ – jpaugh Mar 20 '16 at 19:12
9
\$\begingroup\$

Haskell is very different than other languages.

Here is how I would solve the problem:

import Control.Arrow
import System.Random

uniqueRandomInts :: (RandomGen g, Random a)
    => (a, a) -> Int -> g -> ([a], g)
uniqueRandomInts range n = 
  (map fst &&& snd . last) . take n . iterate getNext . randomR range
  where getNext = randomR range . snd

What does this do?

First note that the g (generator) parameter isn't shown in the example, but it is there.... uniqueRandomInts range n returns a function of type

RandomGen g => g -> ([a], g)

so you will still need to apply this parameter in order to get the values.

I've also refrained from specifying the type of the return value at this stage.... This function is a tool that could be used for any type, why artificially bind it at this point?

The iterate getNext $ randomR range g part (where I've shown where the g will be applied) creates an infinite list of (a, g), where the a's are the random values, and the g's are the generators returned at each step. (for reference, iterate f x is a function that returns [x, f x, (f.f) x, (f.f.f) x, ....]).

Passing around infinite lists is one of those mind blowing things to people who are coming to Haskell from other languages, but remember that the language is lazy, so no actual value will be calculated until requested (this is sort of how the human mind works.... If I ask you to imagine an infinite sequence of 1's, you can reason about it without actually sitting there trying to enumerate all the 1's in your brain before you go on).

We then apply take n to this, to take the first n values of the sequence (thus turning it into something finite before we actually need to calculate any of the values).

Finally, we have the mysterious (map fst &&& snd . last) part. This isn't actually needed for the calculations themselves, but just to format the values in the way that you wanted them. (func1 &&& func2) x applies the functions on the value x, and returns (func1 x, func2 x). We are pulling out the random values in the first slot, and getting the last random generator for the second spot.

You can use this function as follows (because we kept things generic, you need to specify the type)

main = do
  g <- getStdGen
  print $ randomValues (1, 10::Int) 10 g

As to your particular questions:

  1. As to the prefixing, Haskell has a vibrant community ecosystem where many people contribute code to the public, and some sort of prefixing is needed to keep things sane.... Of course this is only needed if you plan to contribute your code. I personally don't prefix at all when I am writing something small for myself (why complicate things?), and can always add it if I need later. If a personal project becomes larger, I can always add it. This is pretty much how I programmed in Java also....

  2. Pre-checking is very common and valuable in Haskell, however.... so is generality. There is no reason that this particular function shouldn't be used by an numerical type over any range (would you want to rewrite the exact same function for a set of random floats over the range -1.0 to +1.0?). I would personally place the limit check and type fixing higher up in the code.... And when I did, I would use the Data.Ix.inRange function.

  3. I didn't use explicit recursion (it was used in a lower level function that I used), however I'll answer the general philosophy that I follow to determine if a subfunction should be top level or not.... I make a function top level if it describes a generic tool that others could use. I usually use a "where" clause generally only for function documentation (ie- when the name of the variable describes what it is doing). Sometimes you need to define a where clause variable for other reasons (ie- recursion or to avoid repetition), but strangely enough these are usually cases that you are better off writing around anyway (recursion and repetition are usually abstracted away in lower level calls like iterate and (&&&), which are cleaner to use anyway). This isn't a hard fast rule though! Not everything can be abstracted in some high level function yet.

  4. I don't know :), however if you ever turn on -Wall in the compiler, it will complain every time you shadow another variable, so to avoid the nagging I usually try to change the name. Sometimes choosing a different name becomes annoying, so I just turn off -Wall :)

EDIT-----

Oops, as you pointed out, I misread the problem.... You need unique values.

Luckily we can still use all the code above, with a slight addition. Add this-

removeDuplicatesUsing::Ord b=>(a->b)->[a]->[a]
removeDuplicatesUsing f theList = [x|(Just x, _, _) <- iterate getNext (Nothing, theList, empty)]
  where 
    getNext (_, x:xs, used) 
      | f x `member` used = (Nothing, xs, used)
      | otherwise = (Just x, xs, insert (f x) used)

Then put one more filter in your randomValue pipeline-

(map fst &&& snd . last) . take n . removeDuplicatesUsing fst . iterate getNext . randomR range

Let me explain what is going on here

  1. There are many algorithms to generate random unique values.... The unique part complicates things a bit, and depending on your circumstances, different algorithms work better. I will discuss those cases later in this answer, but for now I chose the same algorithm that you used in your answer.

  2. Because Haskell is lazy, adding another function filter in a bunch of composed functions barely takes a speed, memory or latancy performance hit. Data will flow through the functions from right to left as it is generated, you will start to see results even before all the data has started to flow into the pipeline. In this way, Haskell function composition is more like Unix pipe chaining than anything else.

  3. In fact breaking things apart like this is my preferred way to do things. By now I might have more code than if I wrote it all in one function, but each of these are simple, easy to debug tools that you could imagine reusing.

  4. A removeDuplicates function (which I didn't write) would read a stream of values in, and filter out anything that it has previously seen. This is almost what we need, but we want to base uniqueness on only the resulting random value (if we included the generator, it would always be unique!). It is common in Haskell to write generalized -Using or -With functions that allow you to pass a function in to give the "key" that you want to use for comparisons (....and note that you can easily define removeDuplicates = removeDuplicatesUsing id).

  5. I wrote the removeDuplicates in the same style as the uniqueRandomInts function (using a list of tuples generated by iterate).... Writing out using recursion here might be easier to read, I guess it is just a matter of taste. This feels more Haskell-y to me, and that was the point of this comparison.

  6. I still left out the range check, but after reading your comment I reverse what I said above, I think it is a good idea to put it in! (I looked too quickly and thought it was a value range, not a count range).


Finally, a note about algorithms (independent on the language chosen to write this). If you are choosing n unique items from a range of N values....

  1. If N and n are small --- It doesn't matter what algorithm you choose, they will all be fast.

  2. If N is huge and n is small --- the given algorithm above works great. It breaks down however....

  3. as n approaches N in size --- Once a sizable percentage of N has been filled, you will start hitting many repeat hits (if 90% of the range has already been taken, only one in 10 tries will get something new). You can of course flip the chosen and not chosen values (ie- generate the 10% you don't want, then return all the others), or you can move on to a solution of this type- https://stackoverflow.com/questions/196017/unique-random-numbers-in-o1. While this is doable in Haskell, the part where you start swapping values in an array is trickier than in any mutable language (you basically either have to use IO around a mutable array, or start making copies of the initial array, which Haskell can do much more efficiently by reusing parts of the initial array in the copied version, but still, less efficient than just doing mutating swaps.... Someone else might have a better suggestion than this....).

  4. If N is really large, holding all values in an array in memory might not be practical. In this case, you might want to use some sort of "unsort" command line tool (a few of these exist in Unix), do a one time pass over all the values, and then take the first n elements of the list.

  5. If N is huge, and you don't care that n come out precisely, you can always do something statistical (do one linear pass and accept each value with probability n/N). This should be much faster than method (4), but of course you won't get exactly n values, and you can't just truncate early, or else you will be favoring earlier values over latter ones.

\$\endgroup\$
  • \$\begingroup\$ Thanks for your reply. However there is nothing above to make the values unique - running with mkStdGen 42 I get [2,2,8,5,7]... My version above uses an IntSet to check for uniqueness. (I originally used an infinite sequence with nub to make them unique, but I believe that is O(n^2) so I used the IntSet to try and improve the bounds. Although it doesn't really matter much on the small values of n I'm using...) How would you go about making the returned list of values unique? \$\endgroup\$ – MrKWatkins Dec 5 '13 at 9:43
  • \$\begingroup\$ Also thanks for inRange, didn't know about that either. Although not sure it will help here. The pre-condition checks I have are basically to stop infinite loops. For example if the range is (1, 10) and n == 11 then I'd get an infinite loop as there are only 10 unique integers available in the range. Similarly I check n is 0 or greater otherwise the recursion will decrement it repeatedly rather than stopping. (Of course it might overflow I guess and eventually stop, but still not what you want...) \$\endgroup\$ – MrKWatkins Dec 5 '13 at 10:27
  • \$\begingroup\$ Oops, you are correct, I missed the word "unique" (right in the title no less :) ). Of course that makes this a more "interesting" problem (in any language). I will add some modifications to the answer later to remedy this. \$\endgroup\$ – jamshidh Dec 5 '13 at 23:43
  • \$\begingroup\$ Thanks for the reply. Haven't had a chance to go through it yet but will do so soon... \$\endgroup\$ – MrKWatkins Dec 9 '13 at 12:32
  • \$\begingroup\$ Still haven't had a chance to go through in detail unfortunately... I'll mark it as the answer though as I'm pretty sure it covers everything. I Might come back to you with more questions at some point though... \$\endgroup\$ – MrKWatkins Jan 6 '14 at 9:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.