在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