Python from Wise Guy's Viewpoint

[Darius]

On Sat, 25 Oct 2003 23:27:46 GMT
prunesquallor at comcast.net wrote:

> I think I have a stumper.  I'll be impressed if a type checker can
> validate this.  The same-fringe function takes a pair of arbitrary
> trees and lazily determines if they have the same leaf elements in the
> same order.  Computation stops as soon as a difference is found so
> that if one of the trees is infinite, it won't cause divergence.

-- this is all sooo pointless in Haskell
data LazyList a
  = Nil 
  | Cons (forall r. ((a,() -> LazyList a) -> r) -> r)

data Tree a = Empty | Leaf a | Fork (Tree a) (Tree a)

-- lazySequence :: LazyList a -> (() -> LazyList a) -> LazyList a
lazySequence Nil      y = y ()
lazySequence (Cons x) y 
    = x (\(xh,xt) -> 
            Cons (\k -> k (xh,(\() -> lazySequence (xt ()) y))))

-- lazyFringe :: Tree a -> LazyList a
lazyFringe Empty      = Nil
lazyFringe (Leaf a)   = Cons (\k -> k (a,\() -> Nil))
lazyFringe (Fork l r) = lazySequence (lazyFringe l)
                                     (\() -> lazyFringe r)

-- lazySame :: Eq a => LazyList a -> LazyList a -> Bool
lazySame Nil Nil = True
lazySame Nil _   = False
lazySame (Cons s1) (Cons s2) 
    = s1 (\(h1,t1) -> 
        s2 (\(h2,t2) -> h1 == h2 && lazySame (t1 ()) (t2 ())))

-- sameFringe :: Eq a => Tree a -> Tree a -> Bool
sameFringe t1 t2 = lazySame (lazyFringe t1) (lazyFringe t2)

testit = test1 && not test2
    where test1 = sameFringe (Fork (Fork (Leaf 1) (Leaf 2)) 
                                   (Fork (Leaf 3) (Fork (Leaf 4) 
                                                        Empty)))
                             (Fork (Leaf 1) 
                                   (Fork (Fork (Leaf 2) (Leaf 3)) 
                                         (Fork (Leaf 4) Empty)))
          test2 = sameFringe (Fork (Fork (Leaf 1) (Leaf 2)) 
                                   (Fork (Leaf 3) cl))
                             (Fork (Leaf 1) 
                                   (Fork (Fork (Leaf 2) (Leaf 3)) 
                                         (Fork (Leaf 3) (Leaf 4))))
          cl = Fork (Leaf 3) cl

testit == True quite unsurprisingly, the example trees aren't -exactly-
the same as the ones in the Lisp version.  This requires one popular
extension to Haskell 98 (rank-2 types).  Of course, all these
shenanigans are unnecessary in Haskell.

I already have a bunch of Church encoded data structures as well if
that's next.