Hacking

[pozorvlak]

I've decided that I should get to learn more about Haskell, because (from what totherme, michiexile and Duncan say) it sounds like it's got much cooler since I last touched it. So today I sat down to write a program to generate valid Siteswaps for juggling patterns. A siteswap is a list of throw heights: "5" means that you throw a ball sufficiently high that the next time it will be thrown is in five beats' time, and so on. So a Three-Ball Cascade is 3, Right Middle Left is 423, and so on. Wikipedia has more information. A candidate pattern is juggleable if you don't have two balls trying to land at the same time.

It took me about three hours and 53 lines, and a lot of that time was spent wrestling with the type system. Debug.Trace was invaluable, though a bit of a pain to use. Anyway, here's the code: do any of you clever Haskell types out there have any comments for how I could have done things better?

-- newtype SiteSwap = SS [Int] deriving (Show, Read, Eq, Ord)
-- this just turned out to be a hassle

collision :: [Int] -> Bool
collision xs = (length (filter (==0) xs)) >= 2

--isJuggleable :: SiteSwap -> Bool
isJuggleable [] = False
isJuggleable ss = isJuggleable' [] 0 (length ss) (cycle ss)

isJuggleable' :: [Int]->Int->Int->[Int]->Bool
isJuggleable' falling fallen maxfallen (s:ss)
        | collision $ map (\x->x-1) falling     = False
-- a pattern is not juggleable if two balls collide
        | fallen > maxfallen            = True
-- a pattern is juggleable if all the initial balls have landed safely
        | otherwise                     = isJuggleable' newfalling newfallen maxfallen ss
                where (newfalling, newfallen) = advance s falling fallen

advance :: Int->[Int]->Int->([Int], Int)
advance height falling fallen = (advanceFalling height falling,
                                 advanceFallen falling fallen)

advanceFalling :: Int->[Int]->[Int]
advanceFalling height falling = height:(filter (>0) (map (subtract 1) falling))
-- Has to be (>0) because of possibility of throwing 0s (ie Gaps)
-- This way, a throw of 0 gets turned to -1 by (subtract 1) and doesn't trigger `collision`.

advanceFallen falling fallen  =  fallen + (length (filter (==0) (map (subtract 1) falling)))

isRepetitive word = or $ map ((flip isRepeated) word) (tail $ reverse $ prefixes word)
-- Lop off the final prefix, which will be the whole word. Else test becomes degenerate

prefixes :: [a]->[[a]]
prefixes []     = []
prefixes (w:ws) = [w]:(map (w:) (prefixes ws))

-- is word a repetition of candidate?
isRepeated candidate word  = isRepeated' (cycle candidate) word
isRepeated' _ []                = True
isRepeated' (c:cs) (w:ws)       | c == w        = isRepeated cs ws
                                | otherwise     = False

finiteLists xs = concat $ map (finiteLists' xs) [0..]

finiteLists' xs 0 = [[]]
finiteLists' xs n = (concat $ outer (:) xs (finiteLists' xs (n-1)))

outer f [] _    = []
outer f (x:xs) ys = (map (f x) ys):(outer f xs ys)

juggleablePatterns = map (concatMap show) $
                        filter (\x -> ((isJuggleable x) && (not $ isRepetitive x))) (finiteLists [1..9])

Now, a quick take 10000 juggleablePatterns should keep me busy for the next several lifetimes...

Comments

[totherme.livejournal.com]

-- newtype SiteSwap = SS [Int] deriving (Show, Read, Eq, Ord)
-- this just turned out to be a hassle

That's because, of the 3 ways in haskell to declare new data types, you've picked the wrong one :)

The three ways are: ["data", "type", "newtype"]

data actually creates a new data structure, using the sort of syntax you were aiming for there. Like "data Tree x = Leaf x | Branch (Tree x, Tree x)" etc...

This is great if you're doing something genuinely new, but there, you weren't. You actually just wanted a list of Ints, but you wanted to refer to them as something else. For that, we have type synonyms. To make your programme do what you want, add the line:

type SiteSwap = [Int]

And do a s/[Int]/SiteSwap/ over the rest of the code. I just tried it in my copy - it works. (there's no need for all the deriving stuff there - the new type has all the properties of the old one, including the ones you were trying to derive)

As for newtype - I believe it does something useful, but I've not yet sat down and read what ;)

[totherme.livejournal.com]

...and of course, I had to go look it up after writing that:

http://www.cs.auckland.ac.nz/references/haskell/haskell-intro-html/moretypes.html

All of this works using a data declaration instead of a newtype declaration. However, the data declaration incurs extra overhead...

So, I feel justified in not bothering about them for the most part ;)

[(Anonymous)]

Ah, cool. Thanks!

To clarify, I'm not (yet) criticizing Haskell's type system, just my own understanding of it. Things are improving: I'm starting to remember some of the common pitfalls and avoiding them.

[totherme.livejournal.com]

To clarify, I'm not (yet) criticizing Haskell's type system

Good, good ;)

Just thinking about that though - it might be worth, when you get what appears to be a spurious type error, taking a copy of the code that produced the error, hiding it, and getting on with your debugging. Then, when you have a working programme, see if the code actually meant what you were thinking at the time - or if real runtime bugs were caught.

Of course, that would have been fairly pointless in this case, since a bug in constructing a type is genuinely one you can avoid by not having types ;)

[pozorvlak.livejournal.com]

Yes, I should have been using that (or better, using version control). A lot of the mistakes have been caused by confusing [a] with [[a]] or the like (hey, in Perl [[a]] would just get flattened :-) ), some have been caused by trying to compose things with two-argument functions (eg not.elem causes a type error), and some have been caused by getting the order of arguments wrong. I didn't find it very helpful yesterday (still learning to read the error messages), but this morning I was starting to find it a bit more helpful - it would screech where I hadn't really thought things through, rather than just everywhere :-)

[totherme.livejournal.com]

Now that the issue was in my head, of course - it didn't take long for it to come up on #haskell:

 beelsebob annotated #28423 with "Nice output" at
             http://paste.lisp.org/display/28423#3 [13:59]
 better
 beelsebob: This is a thing that's been confusing me: Why "newtype KWic =
      K [KWicLine]" rather than "type KWic = [KWicLine]" ? [14:01]
 gds: yes [14:02]
 so that they are different types
 instead of type synonims
 so that you can have a seperate Show instance for it
 Oh, I see :)
 ...and newtype rather than data so that all the other properties default
      to the old type?
 gds: that and the fact that it is essentially a type
            declaration...
 rather than a new ADT
 Ok, cool :) Cheers :)

So, that's why :) For more context about the problem being solved, follow the lisppaste link to "Context in IRC logs".

[totherme.livejournal.com]

And after a few hours of playing, I think I now have some understanding of what a SiteSwap actually is :)

There's only one style point I think I noticed while I was playing, and that's the advance function. Do you really need it? It seems to me that all it does is aggregate one common argument of two distinct 2-arg functions. You could probably do:

        where newfalling = advanceFalling s falling 
              newfallen = advanceFallen falling fallen

...instead. I dunno - doing without advance saves about 1 line in this particular file - if you were using it somewhere else too, the saving would go the other way. Meh :)

As for the rest, it's just knowing what libraries are out there :)

Take a look at Data.List - it contains the function inits, which allows you to refactor prefixes into prefixes = drop 1 . inits - which is pretty cool. It also contains findIndices, which allows us to render prefixes and isRepeated obsolete by redefining:

isRepetitive [] = False
isRepetitive (x:xs) = or $ map cycleAt (findIndices (==x) xs)
    where cycleAt index = take (length xs - index) (cycle (x:(take index xs))) == drop index xs

One cool way to find out about this sort of stuff is with hoogle. There's also a lambdabot plugin that does the same job - which you can also get as part of GHCi On Acid.

Finally:

I thought I had a really cool way of refactoring finiteLists - but it turns out not quite :)

I thought, looking at the output of that function, that what it was doing was actually just counting. So finiteLists xs would count in base (length xs), using the members of xs as symbols. That being the case, I figured it should be possible to define:

finiteLists xs = map (toBase xs) [0..]

...for some appropriate definition of toBase.

I got the definition of toBase that I wanted - and thus discovered that my original idea was flawed:

toBase :: [a] -> Int -> [a]
toBase [] _ = error "You can't count in base 0"
toBase xs i
    | i < 0 = error "Only positive numbers for now"
    | next == 0 = [xs !! i]
    | otherwise = (xs !! (i `mod` base)) : (toBase xs next)
    where base = length xs
          next = i `div` base

(it reverses the order of the output of course:
(reverse $ toBase "0123456789" 65537) == "65537"
...but that's just for ease of list manipulation)

The problem is of course, that finiteLists "abcd" will never produce the string "aa". There's no bug in the code - it's just that when we count: 0 == 00 == 000 == ...

Damn, huh? I thought I was being so cunning there, too :)





(and the end result is more than twice as long as the original 3 line function - lol)

[pozorvlak.livejournal.com]

Aha, nifty. Another problem I came across was that of stripping out words that were cyclic permutations of words that had already occurred - 531 (which is really short for 531531531531531...) is counted as the same pattern as 315 and 153. I wonder if Data.List would help me there? I managed to get it down to four or five lines in the end, and I'm quite proud of the code I wrote to generate the cyclic permutations of a given word:

cyclicPerms xs = take n $ map (take n) $ iterate tail $ cycle xs
       where n = length xs

(from memory)

Unfortunately, this wasn't as serious as the other bug I found - most of the patterns generated aren't actually juggleable! I think my test needs to be made stricter, but I'm not quite sure how :-(

[totherme.livejournal.com]

Can you give examples of patterns which aren't juggleable (but do pass isJuggleable) ?

Ideally, with an explaination as to why they're not juggleable ;)

[totherme.livejournal.com]

Ah! Resource allocation!

I'm guessing that the pattern 4100 isn't juggleable, since:

Since hands alternate, odd-numbered throws send the ball to the other hand, while even-numbered throws send the ball to the same hand.

So, in the pattern 4100, starting with the left, the left hand would always be throwing to itself, and the right hand would always be throwing to the left. So where do the balls come from? And since twice as many balls land in the left as are thrown by it, where do they go?

In my copy of the programme, 4100 passes the isJuggleable test - because it only checks for colisions, not resourcing.

I suppose that might be fixable by crossing your arms at appropriate points to even out the resourcing, but at that stage, my grip on the rules of our model get shakey ;)

[pozorvlak.livejournal.com]

Yes, that's an example. Easy way to test: the average of the throw weights is the number of balls involved in the pattern (aka the capacity), so it has to be an integer (not sure how to prove that, but it seems to work out in practice). 4100 would therefore involve 1.25 balls... unfortunately, this is only a necessary condition for juggleability, and not a sufficient one (in which case this program would be a /lot/ easier to write): for instance, 531 is juggleable, but 135 isn't. Out of the first 100 patterns produced by juggleablePatterns, only 40% have an integer capacity. Of the first 1000 patterns, less than 25% have an integer capacity.

The problem seems most obvious in patterns involving 0 (ie Gaps), but you're right, it may well have to do with resourcing. So you'd have to check that at each throw (unless it has weight 0) there's a ball waiting to be thrown (ie, an entry in the falling queue with height 0). Up to off-by-one errors. The question is, when do you stop checking?

[totherme.livejournal.com]

135 is certainly a resourcing thing. There's a ball thrown at first, which immediately gets re-thrown on the second beat, for a count of three. On the third beat, a second ball is thrown, for a count of five. On the 4th beat we recurse (cycle, whatever) and the instruction is to throw a ball for 1, but no ball's landing, so we need a new one. Now we have a new ball introduced on every cycle, so there's clearly something wrong.

Now, in this case, we've got new balls being introduced, and nowhere for them to go, so there's an inevitable collision, which the code can pick up. This problem can slip by the current code in patterns with 0s in them, I think.

btw - if you present 531 as 153, you have to pick up an extra ball on the second cycle, to make up for only having two in the first - but then the pattern levels out. 135 actually continues demanding more resourses, and obliterating them in colisions ;)

Even without 0s, I suspect that a difficult-to-detect "getting too many balls in/aimed-at one hand, so there's nothing to throw from the other" problem is still possible...

Thinking about your averaging the weights thing (and it's far too late for me to really appriciate that) - I have a vague intuition that in the likes of 135, the 1 spoils the formula by persistantly providing second-hand the ball that 3 would like to mint afresh... So that in some sense, the 1 gets cancelled out, and the true measure of the thing is (3+5)/3 rather than (1+3+5)/3...

Hm - I wonder how blatently wrong that'll look in the morning.... Ah well :)

[pozorvlak.livejournal.com]

Crossing your arms is usually regarded as a separate problem, and dealt with using the Mills' Mess State Transition Diagram... basically, consider the six possible states of hand-holding-ball x crossing, and use the throw weights as your transitions between states.

[pozorvlak.livejournal.com]

There's only one style point I think I noticed while I was playing, and that's the advance function. Do you really need it? It seems to me that all it does is aggregate one common argument of two distinct 2-arg functions.

Ah, yeah, good point. The real reason it's like that is because I originally wrote it as one function (there's code duplicated between advanceFalling and advanceFallen), and had to split it into two to make sense of the compilation errors I was getting. But now it's fixed, I should either refactor them back into one function properly or eliminate advance.

[totherme.livejournal.com]

Oh - and if you want to be able to construct juggleablePatterns from numbers greater than 9, you might want to change concatMap show to map (unwords.show) :)

[pozorvlak.livejournal.com]

The usual approach is to use A for 10, B for 11, and so on. A throw with a weight of Z would have an airtime of 35 beats, and would thus have to be thrown about 1000 times as high as a throw from a three-ball cascade with the same rhythm, so I think we can ignore higher-weight throws for the purposes of discovering human-juggleable patterns :-)

[totherme.livejournal.com]

map (concat $ toBase ([0..9]++['a'..'z'])) ? :)

[stronae.livejournal.com]

I'm tickled that you're using Haskell for this, but I agree that getting used to the type system is a major pain.