ハスケル

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 

私は、その数引数の可変である関数の型を定義する時まで開催されています。

EDIT： nponeccopが言ったように申し訳ありませんが、私は私の仕事を誤解し、私はfunctionToTree :: (a -> b) -> Tree a -> Tree bの書き方を知っていました。それにもかかわらず、私はまだ私の元の質問に不思議です。機能については

     (+) a 
         /\ 
         (+) a 

fは三つのパラメータabc取っ：

は

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

[OK]を、これは私の宿題について、もはやですが ビットを明確にするために、ここで私が考えてきたものです。私はそのような関数を書くことが可能かどうか疑問に思います。 私たちは、このような方法でリストを定義することができます。

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

はそのような一般的な機能を定義することが可能ですか？ 私の質問が理にかなっていないと思うなら、投票してください。

詳細：私は私の質問を洗練しました。私のツリーは、部分的な機能とカレーを説明する別の方法だと思います。

Answer 1

あなたはタスクをよく理解していませんでした。ツリー上に関数をマッピングすることは、ツリーに含まれる各データ要素に関数を適用することである。

数字を含むツリーの描画を開始することをお勧めします。

   1 
     / \ 
      2  3 
      \ /\ 
      4 6 5 

あなたはつまり、NodeとEmptyコンストラクタを持つ表現として木を書き、あなたのTree aデータ型を使用して、このツリーをエンコードすることはできますか？ここで

はいくつかのヒントがあります：

• 最上位ノードは1と二つの非空のサブツリーが含まれています。

• 左のサブツリーには、2、1つの空のサブツリーと1つの空でないサブツリーが含まれています。

• 右側のサブツリーには、3と2つの空でないサブツリーが含まれています。

• レベル3のノードはすべて、サブツリーが空のツリーです。

ここにサンプルツリーを挿入するように投稿を編集します。あなたがそれを行うことができると私たちに示したら、私たちはあなたがさらに進歩するのを助けることができます。

あなたはあなたのツリーを間違って描きました。正しいツリーは：

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

したがって、関数は1つの引数でしかマップできません.2つ、3つ以上ではマップできません。

考え方は、（たとえば）ツリーの各要素に2つを追加できるということです。あなたに合格した場合は、あなたの関数に、例えば

   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

機能的なデータ構造（この場合はツリー）が与えられている場合、通常は2つの一般的なことがあります。あなたが機能f :: a -> b、および構造origTree :: Tree aを取り、newTree :: Tree bで、その結果、構造体の要素に関数を適用どこ

1. マップ
2. 倍

マッピングです。あなたが何らかの形で、いくつかの新しい値に構造体のすべての要素を複合どこ折りたたみ

を（構造マッピング可能を作るための標準的な方法は、それFunctor行い、fmapを定義することであることに注意してください）です。 Treeと(+)の機能を持っていると言ったとき、私はただちに考えました。つまり、ツリー内のすべての要素を合計します。 （！（驚き構造の折り畳み式を作るための標準的な方法は、それFoldableのインスタンスにすることに注意してください）とfoldMapまたはfoldrを定義する）

しかし、あなたの宿題のタスクは、あなたの木のためのマッピング関数を定義することです表示されます。

---

ここで、自分の質問について、関数をツリーに変換します。 a、b、およびcをツリーに入れて、正確に何を意味するのかは不明ですが、少し考えてみましょう。わかりやすくするために、私は完全に汎用的な関数を作るつもりはありません。また、あなたの関数「木」はむしろ偏っているので、私はTreeの代わりにFunHistoryと呼んでいます。これは機能アプリケーションの履歴を表します。

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' 

は、今度は3引数の機能のためにそれを試してみましょう：

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'のように見えます。次のステップは、これらの関数をtypeclassに一般化して、任意の数の入力を持つ関数に拡張することです。キャッチは、すべての入力が同じタイプでなければならないということです。

[警告：このコードはテストされていないが、私は、それはほとんどが正しいですやや確信している...っぽい]

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