一个关于Nested data type的问题

改自这里。

data Fork a = Fork a a
data Perfect a = ZeroP a
               | SuccP (Perfect (Fork a))

Perfect a表示一棵完全二叉树，现在要写个toList :: Perfect a -> [a]函数把它转换成列表。

我先试了type class:

class ToList f where
    toList :: f a -> [a]

instance ToList Fork where
    toList (Fork a b) = [a, b]

instance ToList Perfect where
    toList (ZeroP a) = [a]
    toList (SuccP f) = concatMap toList $ toList f

最后一行是根据类型推出来的，感觉要递归，先看toList f :: [Fork a]，然后就加上concatMap toList然后就搞定了，投机取巧的感觉。

然后再试直接定义，怎么处理SuccP呢：

toList (ZeroP a) = [a]
toList (SuccP f) =
    case f of
      ZeroP (Fork x y) -> [x, y]
      SuccP f2         -> undefined

这里知道 f2 :: Perfect (Fork (Fork a))，递归调用toList f2 ::[Fork (Fork a)]，这么说还需要一个 [Fork (Fork a)] -> [a]的函数就可以了：

toList :: Perfect a -> [a]
toList (ZeroP a) = [a]
toList (SuccP f) =
    case f of
      ZeroP (Fork x y) -> [x, y]
      SuccP f2         ->  flatFork $ flatFork $ toList f2
  where
    flatFork :: [Fork a] -> [a]
    flatFork [] = []
    flatFork ((Fork x y):fs) = [x, y] ++ flatFork fs

还是根据类型把需要的函数补上去而已，而且toList是多态递归的（递归调用时参数类型会改变），必须要写函数签名。

下面再完成另一个方向的转换¹：

fromList []  = Nothing
fromList [x] = Just $ ZeroP x
fromList xs  = do
    let (h, t) = splitAt (length xs `div` 2) xs
    l <- fromList t
    r <- fromList h
    mergePerfect l r

mergePerfect :: Perfect a -> Perfect a -> Maybe (Perfect a)
mergePerfect (ZeroP a) (ZeroP b) = Just $ SuccP (ZeroP (Fork a b))
mergePerfect (SuccP a) (SuccP b) = SuccP <$> mergePerfect a b
mergePerfect _ _ = Nothing

只要分清每个表达式的类型，就很容易推出来。