Add a ratio generator

[gfredericks]

It's an fmap over a pair of integers.

I didn't see any tests of the shrink functions. Do you have any suggestions/preferences for making sure my shrink doesn't do anything weird?

[reiddraper]

Note sure if it matters, but sometimes this produces longs, and not ratios:

user=> (gen/sample gen/ratio)
(-1 -1 1 0 5/2 -1 -3 -7/3 -9/7 -1)
user=> (map type (gen/sample gen/ratio))
(java.lang.Long java.lang.Long clojure.lang.Ratio java.lang.Long java.lang.Long clojure.lang.Ratio java.lang.Long clojure.lang.Ratio clojure.lang.Ratio clojure.lang.Ratio)

I think this is probably fine, since:

user=> (type (/ 1 1))
java.lang.Long

I didn't see any tests of the shrink functions. Do you have any suggestions/preferences for making sure my shrink doesn't do anything weird?

I have a test in mind that I'd like to add to all generators, which is to make sure there are no cycles in the tree. Maybe I'll write that test soon and then we can test this against it.

[gfredericks]

Yeah it's hard to argue for Ratio purity, since even (type (* 3/4 4/3)) is clojure.lang.BigInt.

For your generator test are you going to have to make a generator generator so it can generate generators at random?

[reiddraper]

For your generator test are you going to have to make a generator generator so it can generate generators at random?

Yep. Should be easy with gen/one-of.

My original idea was to do something naive like this to check for cycles (actually, only checking if the root of the tree exists in it's children), but it looks like that might be prohibitive:

(count (tree-seq (constantly true) gen/shrink [5 0 5]))
;;=> 640438

The number of distinct nodes is much smaller though:

(count (set (tree-seq (constantly true) gen/shrink [5 0 5])))
;;=> 79

So maybe something a bit smarter than tree-seq that doesn't shrink the same node (by value) twice would make things much faster.

[reiddraper]

I've been able to write the lazy distinct tree-traversal in Haskell, but am still having trouble writing it in Clojure and making it lazy...

[ztellman]

This isn't quite right, but I'm running out the door and it's at least the right order of magnitude:

> (defn shrink-seq [s]
    (let [seen (atom #{})]
      (tree-seq
        #(if (@seen %) false (do (swap! seen conj %) true))
        gen/shrink
        s)))
#'user/shrink-seq
> (count (shrink-seq [5 0 5]))
462
> (count (distinct (shrink-seq [5 0 5])))
79

I'll try to figure out the actually minimal traversal later.

[reiddraper]

Here's my not-lazy-enough one:

(defn shrink-tree
  [root]
  (let [walk (fn walk [node excludes]
               (lazy-seq
                 (when-not (excludes node)
                   (cons node (first (reduce
                                       (fn [[excludes children] elem]
                                         (let [new-children (walk elem excludes)]
                                           [(into excludes new-children) (into children new-children)]))
                                       [#{} []]
                                      (filter (complement excludes) (shrink node))))))))]
    (walk root #{})))

The reduce here is what's causing it to not be lazy.

In Haskell I can take advantage of whole-program laziness and do:

module Main where

import Test.QuickCheck
import qualified Data.Set as Set

shrinkTree x = fst $ shrinkTree' x Set.empty

shrinkTree' x set = foldr (flip foldHelper) ([x], set) (shrink x)

foldHelper acc@(accList, set) node =
    if Set.member node set
    then acc
    else let recurseResult = shrinkTree' node (Set.insert node set)
         in (accList ++ (fst recurseResult), snd recurseResult)

main :: IO ()
main = print $ shrinkTree (7 :: Integer)

[reiddraper]

@ztellman I thought about using an atom like that too, but would like to figure out how to do it without one. That being said I've already spent quite a bit of time on this (fun) problem... Maybe doing something other than a pre-order depth-first traversal would make it easier?

[reiddraper]

Or maybe doing it CPS style, hmm.

[reiddraper]

Think I have something that works and is sufficiently lazy. The code needs some cleaning up, but the basic idea is that you use a stack to record which nodes you still need to visit, instead of having that be implicit in the call-stack.

(defn make-stack
  [children stack]
  (if-let [s (seq children)]
    (cons children stack)
    stack))

(defn shrink-tree-2
  [root]
  (let [helper (fn helper [node seen stack]
                 (lazy-seq
                   (if-not (seen node)
                     (cons node
                           (if-let [children (seq (shrink node))]
                             (helper (first children) (conj seen node) (make-stack (rest children) stack))
                             (when-let [s (seq stack)]
                               (let [f (ffirst s)
                                     r (rest (first s))]
                                 (helper f (conj seen node) (make-stack r (rest s)))))))
                     (when-let [s (seq stack)]
                       (let [f (ffirst s)
                             r (rest (first s))]
                         (helper f seen (make-stack r (rest s))))))))]
    (helper root #{} '())))

(count (shrink-tree-2 [5 0 5]))
;;=> 79

(count (shrink-tree-2 [10 10 10]))
;;=> 1464

[reiddraper]

Realizing that my tree-walking algorithm actually won't find cycles, but it's a start toward that goal. Some manual testing hasn't shown any problems with the ratio shrinking yet, so I'm going to go ahead and merge it in. We can do some better shrinking testing on all generators later.