Random Schedule Generator

In an attempt to try something new, and possibly help out at work, I tried creating a random schedule generator that generates schedules based on 3 inputs (Rotation length, Staff list, and Shift list), then filters them based on predicates (so far, the only predicate is to make sure that no-one is working longer then X days at a time).

So far, it seems to work, but has 2 issues:

-
It's incredibly slow. Obviously dependent on the computer, but it feels like it's taking longer then I expected it to.

-
It's taking up a ton of memory; even when I set an impossible predicate. Generating a million schedules uses up around 2.5GB of memory. This would be understandable if it was actually collecting a ton of schedules because of a loose restriction, but even when I impose something that results in a empty list (noonesWorkingLongerThen 0days) it still uses a ton of memory; even though in theory, it shouldn't be collecting anything. My only guess is that this is a by-product of lazy evaluation gone wrong somewhere.

Can someone please look it over and point out any bits that could be improved on (either to address my above points, or otherwise)? I'd also like to know if anything I'm doing (habits) are worth continuing.

Note that it's far from done, and isn't very user friendly yet. All the inputs are hard-coded into main().

```
import Data.List
import Data.Maybe
import System.Random

type ShiftList = String
data Day = Day Int [Shift] deriving (Eq, Show)
type Person = String
data Shift = Shift Char Person deriving (Eq, Show)

type Schedule = [Day]

ran = randomRIO

--Assumes that Nothing's have already been filtered
extJust :: Maybe a -> a
extJust (Just a) = a

selectJustsM :: IO [Maybe a] -> IO [a]
selectJustsM mayActs = mayActs >>= return . map extJust . filter isJust

randomElem :: [a] -> IO a
randomElem list = do
let enumLimit = (length list) - 1
r [e] -> IO [e]
shuffle [] = return []
shuffle list = do
re ShiftList -> ShiftList
padShifts nPeople sh

I've started working through a series of revisions in Git of which I'll highlight the best here. Here's the full random-schedule-generator commit log. They're in reverse chronological order so start from the bottom, each is a single small logical modification with my motivations for the change.

First, it doesn't seem slow at all to me. Maybe you're confused by the behavior between testLoop and main? testLoop prints its try messages in between calculating elements of the result list. The resulting [Schedule] is only printed after the function returns control to main, at which point it begins printing what is usually a ~37,000 element list all at once. Also, there is a HUGE difference between running this interpreted from GHCi and running the compiled version (with or without optimizations turned on).

Regarding your second point, there's certainly some poor thunking behavior. What I describe above is one example, those 37,000 Schedules are all kept in memory until they're printed out by main. I'll fix some memory leaks tangentially but not generating 50,000 tries will push memory usage beneath what I'd scrape the barrel for.

The majority of the changes I've made so far involve using functions out of the standard Prelude or from other modules in base to clean up or entirely eliminate some functions. For instance, I ended up replacing your shuffle function with shuffleM from random-shuffle which operates with a better time complexity and in the process threw out randomElem and ran. Here's my commit message with the full detail.


There isn't a list shuffling function provided in anywhere in the base
package, but since it's one of those things that's easier to get
subtly wrong than obviously right I added a dependency on the
random-shuffle package and replaced shuffle with shuffleM (which
operates in an arbitrary MonadRandom monad).


The original implementation of shuffle had O(n^2) complexity, and was
weirdly biased due to the Eq constraint. Consider this:

data Foo = Foo Bool Int
instance Eq Foo where
    (Foo p _) == (Foo q _) = p == q

shuffle [Foo True 1, Foo True 2]
--> suppose randomElem selects Foo True 2
--> re = Foo True 2; restList = [Foo True 2]
== [Foo True 2, Foo True 2]

That may be a pathologic instance of Eq, but even so you wouldn't
expect a shuffle function to drop or duplicate elements.


After switching shuffle functions we can also delete the randomElem
function.

I've still yet to tackle getStretchList or noonesWorkingLongerThen, but I'll hopefully have some time tomorrow to take another pass and think more about architecture and data structures and get to those then as well.

StackExchange Code Review Q#59636, answer score: 2