在Haskell

Question

功能映射到树我们可以定义一个二叉树这样：

data Tree a = Node a (Tree a) (Tree a) 
      | Empty 
      deriving (Show) 

现在我有一个功能，说(+)，我怎么会映射到一个二叉树？我怎样才能将任意函数映射到二叉树？
所以(+) a b将

Node (+) a (Node (+) Empty Empty) (Node a Empty Empty)) 

这是要求我们映射到一棵树的功能和上面是我的理解是一门功课。
函数声明可能是：

functionToTree :: (t1 -> t2) -> Tree a 

我在定义一个函数类型的参数，其数量可变的举起。

编辑： 对不起，因为nponeccop说，我误解了我的任务，我知道怎么写functionToTree :: (a -> b) -> Tree a -> Tree b。尽管我仍然对我最初的问题感到好奇。 为了澄清一点，这里是我一直在想：

     (+) a 
         /\ 
         (+) a 

至于功能f采取三个参数abc：

     f a b 
        / \ 
        f a b 
        /\ 
        f a 

好吧，这不再是我的功课。我只是想知道是否可以编写这样的函数。 我们可以以这样的方式定义的列表：

data Li a = Cons a (Li a) 
      | Empty 
      deriving (Show, Eq, Order) 

是否有可能定义一个一般功能这样呢？ 如果您认为我的问题没有道理，那就请投票吧。

更多：我已经完善了我的问题。我认为我的树是另一种说明部分功能和咖喱的方法。

Answer 1

你没有很好地理解任务。在树上映射函数是将函数应用于树中包含的每个数据元素。

我建议你先画一个包含数字的树。

   1 
     / \ 
      2  3 
      \ /\ 
      4 6 5 

你可以编码使用Tree a数据类型这棵树，就是写树与Node和Empty构造函数表达式？

下面是一些提示：

• 顶部节点包含1和两个非空子树。

• 左子树包含2，一个空子树和一个非空子树。

• 右子树包含3和两个非空子树。

• 三级节点都是空的子树。

编辑您的帖子以在其中插入示例树。一旦你告诉我们你可以做到这一点，我们可以帮助你进一步进行。

你把你的树画错了。正确的树是：

   f 1 
      / \ 
     f 2  f 3 
      \ / \ 
      f 4 f 6 f 5 

所以你只能用一个参数映射功能，但不能有两个，三个或更多。

这个想法是，你可以（例如）为树的每个元素添加两个元素。所以如果你通过

   1 
     / \ 
      2  3   and (\x -> x + 2) or equivalently (+2) 
      \ /\ 
      4 6 5 

你的功能，例如， tree2 = functionToTree (+2) tree1，你回来了修订树：

   3 
     / \ 
      4  5 
      \ /\ 
      6 8 7 

因此，树的每个元素都被替换为新的元素。

Answer 2

给定一个函数式数据结构（在本例中是一棵树），通常可以使用它来做两件大事。

1. 地图
2. 倍

映射是你采取功能f :: a -> b和结构origTree :: Tree a，并应用所述函数应用于所述结构的元素，从而导致newTree :: Tree b。 （请注意，以得到结构可映射的正规途径是使其成为Functor，并定义fmap）

折叠是你莫名其妙化合物结构的所有元素融入了一些新的价值。当你说你有一个Tree和(+)函数，我立即想到了一个折叠：总结树中的所有元素。 （请注意，为了使结构可折叠的正规途径是让它的Foldable（惊喜一个实例！），并定义foldMap或foldr）

但是，看来你的作业任务是定义的映射功能为您的树。现在

---

，关于你自己的问题，把一个函数变成一棵树。通过将a，b和c放到你的树中，你的意思有点不清楚，但让我们稍微思考一下这个想法吧。为了简单起见，我不打算做一个完全通用的函数。另外，由于你的函数“树”相当不平衡，我将它们称为FunHistory而不是Tree。这将代表功能应用程序的历史。

data FunHistory a b = Result b (FunHistory a b) 
        | Application (a -> FunHistory a b) a (FunHistory a b) 
        | Base (a -> FunHistory a b) 

现在这种类型有点奇怪。Result包含b类型的结果，以及以前的函数应用程序的历史链接。 Base包含函数否函数应用程序的历史和产生未来历史的能力，如果提供了类型a的值。 Application则是一个中间记录，它提供了生成未来历史的能力，以及记录过去的历史，以及哪个价值适用于过去的历史。

现在让我们为了方便起见做一些功能。系上安全带，可能会出现颠簸。

mkHist :: (a -> b) -> FunHistory a b 
mkHist f = let h = Base (\x -> Result (f x) h) in h 

给定一个单参数函数，我们可以通过... magic创建一个历史记录。这种特殊的魔法味道被称为“懒惰”和“递归让”。

我们继续前进并创建一个函数，该函数将采用FunHistory和一个输入值，并将历史记录一起移动。可悲的是，这不是一个完整的功能; Result类型的FunHistory未定义。

-- The caller should make sure it isn't a `Result` type before using this function 
app :: a -> FunHistory a b -> FunHistory a b 
app x (Result _ _)  = undefined 
app x (Application f _ _) = f x 
app x (Base f)   = f x 

这是非常愉快的单参数的函数，但从来不需要用于这种简单的情况下的中间Application构造。让我们尝试了2参数的函数创建一个智能构造：

mkHist2 :: (a -> a -> b) -> FunHistory a b 
mkHist2 f = let h = Base (\x -> mkHist' f x h) 
      in h 

mkHist' f x h = let h' = Application (\y -> Result (f x y) h') x h 
       in h' 

让我们尝试它现在是一家三参数功能：

mkHist3 :: (a -> a -> a -> b) -> FunHistory a b 
mkHist3 f = let h = Base (\x -> mkHist2' f x h) 
      in h 

mkHist2' f x h = let h' = Application (\y -> mkHist' (f x) y h') x h 
       in h' 

现在的4参数功能：

mkHist4 :: (a -> a -> a -> b) -> FunHistory a b 
mkHist4 f = let h = Base (\x -> mkHist3' f x h) 
      in h 

mkHist3' f x h = let h' = Application (\y -> mkHist2' (f x) y h') x h 
       in h' 

那么看看那个;这些功能看起来几乎完全相同mkHist3和mkHist2'！从这里开始的下一步将是将这些函数泛化为一个类型类型，以便它可以扩展到具有任意数量输入的函数。问题在于所有输入必须具有相同的类型。

[警告：此代码是未经测试，但我有点肯定它主要是正确的...... ISH]

instance (Show a, Show b) => Show (FunHistory a b) where 
    show (Base _) = "base" 
    show (Application _ x h) = "app " ++ show x ++ ", " ++ show h 
    show (Result r h) = "result: " ++ r ++ ", " ++ show h