1. ホーム
  2. haskell

[解決済み] Haskellバイナリツリー

2022-02-19 11:01:55

質問

宿題があります。

1) データ構造を定義する TTT ここで、各頂点は0、1または2の子を持ち、各樹木の葉(0個の子を持つ頂点とそれ自身)は自然数のリストを含んでいます。

2) 関数を作成する mm これは2つの引数を持ちます - 関数 f(Integer->Integer)TTT ベースツリー x . その結果、次のようになります。 TTT をベースにしたツリーです。 x 機能を使って f をリストの各要素に適用します(1)の定義に参照).

機能 f は、以下の表現を持つことができます( a , b または c ):

a :: Integer -> Integer
a x = x * x

b :: Integer -> Integer
b x = x `mod` 9

c :: Integer -> Integer
c x = x * x * x

どなたか教えてください。

どのように解決するのですか?

重要なアドバイス

を通して作業する価値があると思います。 ハスケルを学べば、いいことがある . 素晴らしいチュートリアルです。

実践! 遊べ! この課題を拡張して、概要を変更してください。整数の代わりに文字列を扱うことができますか?3つのサブツリーを持つツリーを作成できますか?枝にもデータを持たせることができますか?任意のデータ型を受け取るツリーを作ることができますか?について調べましょう。 Functor s. なぜ良いのでしょうか?計算を表す木で、次のような操作を表す枝を作ることができますか? + 葉っぱは数字?

遊べば遊ぶほど、自信がつく。クラスで、何かを先に発見した人になりましょう。みんながあなたに助けを求めるようになり、グループの誰もが抱える厄介な問題を解くように言われたとき、あなたはさらに学ぶことになるでしょう。

問題1:木のデータ型

以下はそのヒントです。

この二分木は、2つのサブツリーまたはブールリーフを持つ。

data BTree = Leaf Bool | Branch BTree BTree 
  deriving (Eq,Show)

このデータ構造には3つの項目があり、そのうちの1つは Bool s:

data Triple = Triple Int String [Bool]
  deriving (Eq,Show)

こちらは3種類の可能性があり、なぜなら Expr が右側に表示されるので、ちょっとツリーみたいですね。

data Expr = Var Char | Lam Char Expr | Let Char Expr Expr
  deriving (Eq,Show)

今度は、3つの可能性を持つものが必要です。葉は整数のリストを持ち、他の2つは1つのサブツリー、または2つのサブツリーを持っています。例題にあるようなアイデアをまとめてみましょう。

問題2:木に関数を写す

これを「関数適用型どこでもマップ」と呼び、関数をpingで送信します。 map はリストに対してそれを行い fmap は他のものにも使えます。

を受け取る関数を定義してみましょう。 Bool -> Bool を作成し、最初の例の上にマッピングします。

mapBTree :: (Bool -> Bool) -> BTree -> BTree
mapBTree f (Leaf b) = Leaf (f b)
mapBTree f (Branch b1 b2) = Branch (mapBTree f b1) (mapBTree f b2)

と、トリプルの上にマッピングするもう一つのものがあります。今回は、それぞれの Bool をリスト化した。

mapBoolTriple :: (Bool -> Bool) -> Triple -> Triple
mapBoolTriple f (Triple i xs bs) = Triple i xs (map f bs)

標準的な関数である map というもので、このように動作します。

map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs

を適用するようにします。 f をそれぞれの x を先頭から順番に表示するようにしました。

私なら本当はこんな風にする

しかし、これは私が実際に行う方法ではない。私なら

{-# LANGUAGE DeriveFunctor #-}

をファイルの先頭に書くと、次のようになります。

data BinTree a = ALeaf a | ABranch (BinTree a) (BinTree a)
   deriving (Eq, Show, Functor)

を実行することができます。

fmap (*100) (ABranch (ALeaf 12) (ALeaf 34))

とすると

ABranch (ALeaf 1200) (ALeaf 3400)

しかし fmap の方がより柔軟です。また

fmap (<20) (ABranch (ALeaf 12) (ALeaf 34))
  -- ABranch (ALeaf True) (ALeaf False)

または

fmap show (ABranch (ALeaf 12) (ALeaf 34))
 -- ABranch (ALeaf "12") (ALeaf "34")

この関数を一行も書かずに fmap . その場合、追加の言語機能を使ったという点では10点満点ですが、設定された問題を解いたという点では0点満点になると思いますので、そのようなことはしないで、心に留めておいて、使えるときに使ってください。

その他のアドバイス

Haskellを楽しく学んでください。時には頭が真っ白になることもありますが、学習した分、強く報われます。Haskellのプログラムは、従来の言語のプログラムの10分の1の長さで書けるようになります。もっと考えよう! もっと考えて!もっと少なく書いて