samefringe problem

プログラミング

このまえ、考えるといっていたやつ。
http://practical-scheme.net/wiliki/wiliki.cgi?Shiro

data Tree a = Leaf a | Branch [Tree a]

fringe :: Tree a -> [a]
fringe (Leaf x)   = [x]
fringe (Branch x) = foldr (\x r -> fringe x ++ r) [] x

samefringe :: Eq a => Tree a -> Tree a -> Bool
samefringe x y = fringe x == fringe y

ただ、Haskellの文法とライブラリはよく知らないので、Concurrent Cleanの文法と似たようなものだと思って、考えてみる。

１．

samefringe x y

２．

fringe x == fringe y

３．

fringe (Branch [x1:x2]) == fringe (Branch [y1:y2])

４．

(==)
  ( foldr (\x r -> fringe x ++ r) [] [x1:x2] )
  ( foldr (\x r -> fringe x ++ r) [] [y1:y2] )

５．

(==)
  ( (\x r -> fringe x ++ r) x1 (foldr (\x r -> fringe x ++ r) [] x2) )
  ...

６．

(==)
  ( fringe x1 ++ (foldr (\x r -> fringe x ++ r) [] x2) )
  ...

７．

(==)
  ( fringe (Leaf x3) ++ (foldr (\x r -> fringe x ++ r) [] x2) )
  ...

８．

(==)
  ( [x3] ++ (foldr (\x r -> fringe x ++ r) [] x2) )
  ( [y3] ++ (foldr (\x r -> fringe x ++ r) [] y2) )

９．

(==)
  (x3 : (foldr (\x r -> fringe x ++ r) [] x2))
  (y3 : (foldr (\x r -> fringe x ++ r) [] y2))

１０．

  | x3 == y3
    = (==)
         (foldr (\x r -> fringe x ++ r) [] x2)
         (foldr (\x r -> fringe x ++ r) [] y2)
    = False