这是一个有文化的haskell帖子。只需将其保存为“ChurchList.lhs”即可运行。
> {-# LANGUAGE Rank2Types #-}
Church 编码列表是一种通过函数表示列表的方式。它类似于弃牌和连续传球风格。
> newtype ChurchList a = CList {runCList :: forall r. (a -> r -> r) -> r -> r}
为了说明这如何对应于一个列表,这里是一个 O(n) 同构
> fromList :: [a] -> ChurchList a
> fromList xs = CList $ \cons empty -> foldr cons empty xs
> toList :: ChurchList a -> [a]
> toList cl = runCList cl (:) []
> instance Show a => Show (ChurchList a) where
> show cl = "fromList " ++ show (toList cl)
这些东西具有良好的性能特征。
> singleton :: a -> ChurchList a -- O(1)
> singleton a = CList $ \cons empty -> a `cons` empty
> append :: ChurchList a -> ChurchList a -> ChurchList a -- O(1)!!! This also means cons and snoc are O(1)
> append cl1 cl2 = CList $ \cons empty -> runCList cl1 cons (runCList cl2 cons empty)
> concatCl :: ChurchList (ChurchList a) -> ChurchList a -- O(n)
> concatCl clcl = CList $ \cons empty -> runCList clcl (\cl r -> runCList cl cons r) empty
> headCl :: ChurchList a -> Maybe a -- O(1)
> headCl cl = runCList cl (\a _ -> Just a) Nothing
现在,问题来了tail
。
> tailClbad :: ChurchList a -> Maybe (ChurchList a) --O(n)?!!
> tailClbad cl = (fmap snd) $ runCList cl
>
> (\a r -> Just (a, case r of
> Nothing -> CList $ \cons empty -> empty
> Just (s,t) -> append (singleton s) t)) --Cons
>
> Nothing --Empty
基本上我的实现所做的是将列表分成头部和尾部。Cons 替换了头部,并将旧的头部附加到尾部。这是相当低效的。似乎教会列表在拆分方面通常效率低下。
我希望我错了。有没有tailCl
比 O(n) 更好的实现(最好是 O(1))。