haskell - 在Haskell中使用折叠功能查找树高

我要完成的一项工作是准备考试

data Exp =  T | F | And Exp Exp | Or Exp Exp | Not Exp deriving (Eq, Show, Ord, Read)

然后要求
folde :: a -> a -> (a -> a -> a) -> (a -> a -> a) -> (a -> a) -> Exp -> a
这就是我想出的

folde :: a -> a -> (a -> a -> a) -> (a -> a -> a) -> (a -> a) -> Exp -> a
folde t f a o n T = t
folde t f a o n F = f
folde t f a o n (And x y) = a (folde t f a o n x) (folde t f a o n y)
folde t f a o n (Or x y) = o (folde t f a o n x) (folde t f a o n y)
folde t f a o n (Not x) = n (folde t f a o n x)

分配要求evb，evi和evh。

它们都应该使用正确的参数通过一次调用来进行折页。

Evb计算 bool 表达式。

evb :: Exp -> Bool
evb = folde True False (&&) (||) not

Evi计算一个整数，将T当作Int 1，F当作Int 5，And当作+，Or当作*，Not当作否定值。

evi :: Exp -> Int
evi = folde 1 5 (+) (*) negate

到目前为止，一切正常。我也很高兴对此有任何反馈。

但是，我似乎无法理解如何解决evh。evh应该用于计算树的高度。

应该是evh :: Exp -> Int
作业说应将T和F视为高度1。
继续，Not x应该评估为height x + 1。 And和Or具有height of its tallest subtree + 1。

我似乎无法弄清楚应将什么传递给folde函数

最佳答案

您可以使用显式递归直接直接编写以下代码:

height T = 1
height F = 1
height (Not x) = height x + 1
height (And x y) = max (height x) (height y) + 1
height (Or  x y) = max (height x) (height y) + 1

现在，如何用folde编写此代码？递归折叠的关键是folde为您的每个函数提供折叠所有子树的结果。当您在folde上使用And l r时，它首先折叠两个子树，然后将这些结果传递到folde的参数中。因此，代替您手动调用height x，folde将为您计算该值并将其作为参数传递，因此您自己的工作最终类似于\x y -> max x y + 1。本质上，将height分为5个定义(每个构造函数一个)，而不是对子树进行分解和递归，而是将子树的高度作为参数:

heightT = 1 -- height T = 1
heightF = 1 -- height F = 1
heightN x = x + 1 -- height (Not x) = height x + 1
heightA l r = max l r + 1 -- height (And l r) = max (height l) (height r) + 1
heightO l r = max l r + 1 -- height (Or  l r) = max (height l) (height r) + 1

将它们输入folde，并简化

height = folde 1 1  -- T F
               ao   -- And
               ao   -- Or
               (+1) -- Not
         where ao x y = max x y + 1

现在换个新东西吧!采取以下定义:

data ExpF a = T | F | Not a | And a a | Or a a
              deriving (Functor, Foldable, Traversable)

看起来像Exp，除了没有递归，它有一个类型参数和一堆用于该类型值的孔。现在，看看ExpF下的表达式类型:

T :: forall a. ExpF a
Not F :: forall a. ExpF (ExpF a)
And F (Not T) :: forall a. ExpF (ExpF (ExpF a))

如果您在上述每种方法中都将a = ExpF (ExpF (ExpF (ExpF (ExpF ...))))设置为on(无穷大)，则会发现它们都可以具有相同的类型:

T             :: ExpF (ExpF (ExpF ...))
Not F         :: ExpF (ExpF (ExpF ...))
And F (Not T) :: ExpF (ExpF (ExpF ...))

无限乐趣!我们可以使用Fix对这种无限递归类型进行编码

newtype Fix f = Fix { unFix :: f (Fix f) }
-- Compare
-- Type  level: Fix f = f (Fix f)
-- Value level: fix f = f (fix f)
-- Fix ExpF = ExpF (ExpF (ExpF ...))
-- fix (1:) =    1:(   1:(  1: ...))
-- Recover original Exp
type Exp = Fix ExpF
-- Sprinkle Fix everywhere to make it work
Fix T :: Exp
Fix $ And (Fix T) (Fix $ Not $ Fix F) :: Exp
-- can also use pattern synonyms
pattern T' = Fix T
pattern F' = Fix F
pattern Not' t = Fix (Not t)
pattern And' l r = Fix (And l r)
pattern Or' l r = Fix (Or l r)
T' :: Exp
And' T' (Not' F') :: Exp

现在，这是一个不错的部分:fold的一种定义来统治它们:

fold :: Functor f => (f a -> a) -> Fix f -> a
fold alg (Fix ffix) = alg $ fold alg <$> ffix
-- ffix :: f (Fix f)
-- fold alg :: Fix f -> a
-- fold alg <$> ffix :: f a
-- ^ Hey, remember when I said folds fold the subtrees first?
-- Here you can see it very literally

这是一个单字height

height = fold $ \case -- LambdaCase extension: \case ... ~=> \fresh -> case fresh of ...
  T -> 1
  F -> 1
  Not x -> x + 1
  And x y -> max x y + 1
  Or  x y -> max x y + 1

现在是一个非常多态的height(在您的情况下，它是一个关闭；哦，很好)。

height = fold $ option 0 (+1) . fmap getMax . foldMap (Option . Just . Max)
height $ Fix T -- 0
height $ Fix $ And (Fix T) (Fix $ Not $ Fix F) -- 2

请参阅recursion-schemes包以学习这些黑暗艺术。它还使该操作适用于带有类型族的基本类型(如[])，并且无需使用欺骗性和某些TH来对所有内容进行Fix。

关于haskell - 在Haskell中使用折叠功能查找树高，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/47242294/