[解決済み] Haskellバイナリツリー
質問
宿題があります。
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の長さで書けるようになります。もっと考えよう! もっと考えて!もっと少なく書いて
関連
-
[解決済み] Haskell - Ord aの型は何を意味するのでしょうか?
-
[解決済み] Haskell タプルをリスト化する?
-
[解決済み] モナドはエンドファンクタのカテゴリではただのモノイドですが、何か問題でも?
-
[解決済み】2分木と2分探索木の違いについて
-
[解決済み] Haskell における `mod` と `rem` の違い
-
[解決済み】Haskellの入門編
-
[解決済み] CabalとStackの違いは何ですか?
-
[解決済み] ハスケル Where vs. Let
-
[解決済み] レコードの単一フィールドを割り当て、残りのフィールドはコピーするための省略記法?
-
[解決済み] HaskellとF#の主な違いは何ですか?[クローズド]
最新
-
nginxです。[emerg] 0.0.0.0:80 への bind() に失敗しました (98: アドレスは既に使用中です)
-
htmlページでギリシャ文字を使うには
-
ピュアhtml+cssでの要素読み込み効果
-
純粋なhtml + cssで五輪を実現するサンプルコード
-
ナビゲーションバー・ドロップダウンメニューのHTML+CSSサンプルコード
-
タイピング効果を実現するピュアhtml+css
-
htmlの選択ボックスのプレースホルダー作成に関する質問
-
html css3 伸縮しない 画像表示効果
-
トップナビゲーションバーメニュー作成用HTML+CSS
-
html+css 実装 サイバーパンク風ボタン
おすすめ
-
[解決済み] 一般的に `{- |` で始まるHaskellのコメントは何を意味するのですか?
-
[解決済み] 解釈の仕方 (Eq a)
-
[解決済み] Haskellバイナリツリー
-
[解決済み] 読んで学ぶべき良いHaskellのソース [終了しました]。
-
[解決済み] Haskellで副作用がモナドとしてモデル化されているのはなぜですか?
-
[解決済み] 制約条件付き特殊化
-
[解決済み] なぜ依存型でないのか?
-
[解決済み] CabalとStackの違いは何ですか?
-
[解決済み] レコードの単一フィールドを割り当て、残りのフィールドはコピーするための省略記法?
-
[解決済み] Haskell型とデータコンストラクタ