ハスケルへのとげを通して。 1/2

Haskellの短くて難しい紹介の最初の部分。 2番目の部分はここにあります。



tl; dr ：Haskellの非常に短く簡潔な紹介。

• はじめに
  
  
  • 設置
  • パニックなし
  • Haskellの基本
    
    
    • 関数宣言
    • 型を使用した例
    
    
    
  
  
  
• Haskellからの最低限必要なもの
  
  
  • 表現
    
    
    • 算術
    • 論理的
    • べき乗
    • リスト
    • 行
    • タプル
    • 括弧を扱います
    
    
    
  • 関数を書くのに役立つこと
  
  
  
• 難しい部分
  
  
  • 機能的なスタイル
    
    
    • 高階関数
    
    
    
  • 種類
    
    
    • 型推論
    • 新しいタイプの作成
    • 再帰型
    • 木々
    
    
    
  • 無限の構造
  
  
  

UPD。 チュートリアルが気に入ったら、 元の記事の著者に数行をドロップしてください 。 人は喜んでいます;）



私はすべての開発者がHaskellを学ぶべきだと本当に信じています。 誰もがスーパーハスケル忍者になるべきではないと思います。 人々は、Haskellが提供する機会に注意する必要があります。 Haskellを学習すると、意識が広がります。





主流の言語は非常に似ています

• 変数
• サイクル
• ポインター（ほとんどの言語がこの事実を隠そうとしても、依然として事実のままです）
• 構造、オブジェクト、およびクラス（ほとんどの言語）

Haskellはそれらとは大きく異なります。 この言語は、これまで聞いたことがない概念の束を使用しています。 これらの概念の多くは、より優れたプログラマーになるのに役立ちます。





しかし、Haskellの学習は難しい場合があります。 少なくとも私にとっては難しいことでした。 そしてこの記事では、勉強の過程で欠けていたものを見せようとします。



この記事をマスターするのは難しいでしょう。 これは意図的に行われました。 Haskellを学ぶ簡単な方法はありません。 この道は難しくて難しいです。 しかし、それは良いことだと思います。 興味深いのは、Haskellの複雑さだからです。



Haskellを習得する通常の方法は、2冊の本を読むことです。

最初に「Learn You a Haskell」 、次に「Real World Haskell」 。



これが学習への正しいアプローチであることに同意します。 しかし、Haskellが何であるかを理解するには、これらの本を非常に注意深く読む必要があります。





一方、この記事はHaskellのすべての基本的な側面を非常に簡潔かつ簡潔に紹介しています。 Haskellを勉強したときに欠けていたニュアンスもいくつか追加しました。





この記事は5つのパートで構成されています。

• はじめに：Haskellが恐れを知らないことを示す短い例です。
• Haskellの基本：Haskell構文といくつかの基本構造。
• 難しい部分：
  
  
  • 機能的なスタイル; 命令型から機能型への移行の例
  • タイプ; タイプと標準の二分木の例
  • 無限の構造; 無限の二分木で動作します！
  
  
  
• くそー難しい部分：
  
  
  • IOを扱います。 最小限の例
  • IOを使用したトリックの分析。 私を理解するのを妨げた明白でない些細なこと
  • モナド 非現実的に強力な抽象化ツール
  
  
  
• アプリケーション：
  
  
  • 無限の木についてのもう少しの言葉; 無限の木の数学指向の議論
  
  
  

注：ファイル名と拡張子が.lhs



区切り文字が表示される.lhs



、

ダウンロードできます。

ファイルをfilename.lhs



として保存すると、次のfilename.lhs



で実行できます。

runhaskell filename.lhs





いくつかの例は動作しないかもしれませんが、ほとんどは動作するはずです。

以下に、ファイルへのリンクが表示されます

---

01_basic / 10_Introduction / 00_hello_world.lhs

はじめに

設置

• Haskellプラットフォームは、Haskellをインストールする標準的な方法です。

ユーティリティ：

• ghc
  
  
  
  ： C
  
  
  
  gccに似たコンパイラ
• ghci
  
  
  
  ：Haskellインタラクティブシェル（REPL）
• runhaskell
  
  
  
  ：コンパイルせずにプログラムを実行します。 便利ですが、コンパイルされたプログラムに比べて非常に遅いです。

パニックなし

多くの本や記事は、いくつかの難解な公式（クイックソート、フィボナッチなど）でHaskellを知っています。 私は異なった行動をします。 Haskellの超大国をすぐには見せません。 Haskellが他のプログラミング言語に似ているものに集中します。 それでは、おなじみの「Hello World」から始めましょう。

 main = putStrLn "Hello World!"
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

実行するには、このコードをhello.hs



として保存し、 hello.hs



を実行します。

  ~ runhaskell ./hello.hs Hello World!
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

「はじめに」の下にあるリンクからソースをダウンロードできます



ファイル00_hello_world.lhs



を保存して実行します。

  ~ runhaskell 00_hello_world.lhs Hello World!
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

01_basic / 10_Introduction / 00_hello_world.lhs

---

01_basic / 10_Introduction / 10_hello_you.lhs



次に、名前を尋ねて「こんにちは、名前！」と言うプログラムを作成します。

 main = do print "  ?" name <- getLine print (" " ++ name ++ "!")
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

まず、他の命令型言語と例を比較してください。

 # Python print "  ?" name = raw_input() print " %s!" % name
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

 # Ruby puts "  ?" name = gets.chomp puts " #{name}!"
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

 // In C #include <stdio.h> int main (int argc, char **argv) { char name[666]; // <-  ! //  ,     665 ? printf("  ?\n"); scanf("%s", name); printf(" %s!\n", name); return 0; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

プログラムの構造は非常に似ていますが、わずかな構文上の違いがあります。 チュートリアルの主要部分では、これらの違いを正確に説明します。





Haskellでは、各関数とオブジェクトには独自の型があります。

main



関数のタイプはIO ()



です。

これは、実行時にmain



が副作用を引き起こすことを意味します。



しかし、Haskellが通常の命令型言語のように見えることを忘れないでください。



01_basic / 10_Introduction / 10_hello_you.lhs

---

01_basic / 10_Introduction / 20_very_basic.lhs

最も基本的なHaskell

続行する前に、Haskellの特別な機能のいくつかについて警告したいと思います。



機能性



Haskellは関数型言語です。

命令型言語で始めた場合、多くの新しいことを学ぶ必要があります。

幸いなことに、これらの概念の多くは、命令型言語でもプログラムの改善に役立ちます。



高度な静的型付け



C



やC++



、 Java



ように邪魔する代わりに、型システムが役立ちます。



清潔さ



一般的に言えば、あなたの機能は外の世界では何も変えません。

一方で、これは、関数が変数の値を変更できず、ユーザーからデータを受信できず、画面に書き込むことができず、ロケットを発射できないことを意味します。

一方、プログラムの並列化は簡単です。

Haskellは、純粋な関数と副作用を引き起こす関数との間に明確な線を引きます。

このアプローチにより、プログラムのプロパティを分析するのがはるかに簡単になります。

プログラムの機能的にきれいな部分では、コンパイル段階で多くのエラーが除外されます。





さらに、機能的に純粋な関数は、基本的なHaskellの法則に従います。

同じパラメーターを使用した関数呼び出しは、常に同じ結果をもたらします。

怠azine



デフォルトの遅延は、プログラミング言語では非常に珍しいことです。

デフォルトでは、Haskellは本当に必要な場合にのみ値を評価します。

その結果、無限のデータ構造を非常に簡単に扱うことができます。



最後の警告は、Haskellのコードを読む価値があるかどうかに関係します。

私にとって、これは科学論文を読むようなものです。

一部の部分は単純明快かもしれませんが、式が見られる場合は、集中して読んでください。

Haskellを学習するとき、構文の機能の一部を完全に理解していなくても問題はありません。

>>=



、 <$>



、 <-



などの恐ろしい文字を思いついた場合は、それらを無視して、コードの一般的な考え方を理解してください。

関数定義

次のように関数を定義できます。



C



：

 int f(int x, int y) { return x*x + y*y; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Javascriptの場合：

 function f(x,y) { return x*x + y*y; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Pythonの場合：

 def f(x,y): return x*x + y*y
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Rubyの場合：

 def f(x,y) x*x + y*y end
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

スキームについて：

 (define (fxy) (+ (* xx) (* yy)))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そして最後に、Haskell：

 fxy = x*x + y*y
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

非常に明確です。 括弧なし、 def



なし。



Haskellは関数と型を多用していることに注意してください。

したがって、それらは非常に簡単に識別できます。

言語の構文は、定義をできるだけ単純にするために考案されました。

新しいタイプを作成する例

通常、プログラムを作成するときに、関数のタイプを指定します。

しかし、これは必要ありません。

コンパイラーは、これを行うのに十分スマートです。



少し遊びましょう。

 --     :: f :: Int -> Int -> Int fxy = x*x + y*y main = print (f 2 3)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

 ~ runhaskell 20_very_basic.lhs 13
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

01_basic / 10_Introduction / 20_very_basic.lhs

---

01_basic / 10_Introduction / 21_very_basic.lhs



今すぐ試してください

 f :: Int -> Int -> Int fxy = x*x + y*y main = print (f 2.3 4.2)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

エラーが表示されます：

 21_very_basic.lhs:6:23: No instance for (Fractional Int) arising from the literal `4.2' Possible fix: add an instance declaration for (Fractional Int) In the second argument of `f', namely `4.2' In the first argument of `print', namely `(f 2.3 4.2)' In the expression: print (f 2.3 4.2)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

問題は4.2



がIntではないことです。



01_basic / 10_Introduction / 21_very_basic.lhs

---

01_basic / 10_Introduction / 22_very_basic.lhs



1つの解決策は、関数f



タイプを明示的に指定しないことです。

次に、Haskellが最も一般的な適切なタイプを推測します。

 fxy = x*x + y*y main = print (f 2.3 4.2)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

稼いだ！

素晴らしい、各データ型に新しい関数を作成する必要はありません。

たとえば、 C



では、 int



、 float



、 long



、 double



などの関数を作成する必要があります。



しかし、どのタイプを示す必要がありますか？

Haskellがどのタイプを推測したかを理解するには、単にghciを実行します：

 % ghci GHCi, version 7.0.4: http://www.haskell.org/ghc/ :? for help Loading package ghc-prim ... linking ... done. Loading package integer-gmp ... linking ... done. Loading package base ... linking ... done. Loading package ffi-1.0 ... linking ... done. Prelude> let fxy = x*x + y*y Prelude> :type f f :: Num a => a -> a -> a
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

うーん...これはどんな奇妙なタイプですか？

 Num a => a -> a -> a
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

まず、a- a -> a -> a



右側に注意してください。

それを理解するために、いくつかの例を見てみましょう。

指定されたタイプ	価値
Int	タイプInt
Int -> Int	入力Int を受け取り、 Int を返す関数
Float -> Int	Float を受け入れ、 Int を返す関数
a -> Int	入力として任意の型を取り、 Int を返す関数の型
a -> a	入力タイプa を受け取り、タイプa 結果を返す関数のタイプ
a -> a -> a	入力としてタイプa 2つの引数を取り、タイプa の結果を返す関数のタイプ

タイプa -> a -> a



では、文字a



はタイプ変数です 。

つまり、 f



は2つの引数の関数であり、両方の引数と結果は同じ型です。

タイプa



変数は、さまざまなタイプの値を取ることができます。

たとえば、 Int



、 Integer



、 Float



...



したがって、 C



ように型をハードに設定する代わりに、 int



、 long



、 float



、 double



などの関数を個別に定義します...

動的に型付けされた言語のように、1つの関数を作成するだけです。



一般的に、 a



はどのタイプでもかまいません。

Trees



、別の関数型などのより複雑な型のString



、 Int



。

しかし、この例では、型には接頭辞Num a =>



が付いています。



Num



は型クラスです。

型クラスは、多くの型として表すことができます。

Num



は、数値のように動作する型のみが含まれます。

より厳密には、 Num



は特定の関数セット、特に(+)



と(*)



を実装する型を含むクラスです。



型クラスは、言語の非常に強力な要素です。

彼らの助けを借りて、私たちは素晴らしいことをすることができます。

しかし、これについては少し後で説明します。



したがって、 Num a => a -> a -> a



と書くとNum a => a -> a -> a



ことを意味します。



a



Num



型クラスに属する型にします。

これは、入力としてaを受け取り、（a- a -> a



）を返す関数です。



うーん、それは奇妙です。

実際、Haskellでは、2つの引数を入力として受け入れる関数はありません。

代わりに、すべての関数には引数が1つしかありません。

ただし、2つの引数の関数は、最初の引数を取り、2番目の引数をパラメーターとして取る関数として返すことができることに注意してください。

。



つまり、 f 3 4



(f 3) 4



f 3 4



同等です。

f 3



も関数であることに注意してください。

 f :: Num a :: a -> a -> a g :: Num a :: a -> a g = f 3 gy ⇔ 3*3 + y*y
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

別のエントリを使用して関数を作成することもできます。

ラムダ式を使用すると、名前を付けずに関数を作成できます。

これらは匿名関数とも呼ばれます。

私たちは書くことができます：

 g = \y -> 3*3 + y*y
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

\



文字は、 λ



文字に似ているため使用されますが、同時にASCII文字です。



関数型プログラミングが初めての場合、この時点で脳は沸騰し始めます。

実際のアプリケーションを作成します。



01_basic / 10_Introduction / 22_very_basic.lhs

---

01_basic / 10_Introduction / 23_very_basic.lhs



ただし、開始する前に、型システムが正常に機能することを確認する必要があります。

 f :: Num a => a -> a -> a fxy = x*x + y*y main = print (f 3 2.4)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このコードは、 3



がFloat型の小数（小数）とInteger型の整数の両方を表すことができるため機能します。

2.4



は分数型であるため、 3



も分数として表されます。



01_basic / 10_Introduction / 23_very_basic.lhs

---

01_basic / 10_Introduction / 24_very_basic.lhs



関数に他の型を書くと、機能しなくなります：

 f :: Num a => a -> a -> a fxy = x*x + y*y x :: Int x = 3 y :: Float y = 2.4 main = print (fxy) --   ,   x ≠  y
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

コンパイラはエラーを通知します。

2つのパラメーターは同じタイプでなければなりません。



これが悪い考えであり、コンパイラーが型を変換する必要があると思う場合、本当に素晴らしいビデオを見る必要があります。

ワット



01_basic / 10_Introduction / 24_very_basic.lhs

Haskellの最小要件

このセクションをすぐに確認することをお勧めします。

それを参考資料と考えてください。

Haskellは非常に多面的な言語です。

したがって、このセクションのいくつかのことはスキップされます。

必要に応じて、何かがおかしい、または理解できないと思われる場合は、ここに戻ってください。



シンボル⇔



を使用して、2つの式の等価性を示します。

これはメタ表記です; Haskellにははありません。

記号⇒



は、式の評価結果を示すために使用されます。

表現

算術

 3 + 2 * 6 / 3 ⇔ 3 + ((2*6)/3)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

論理的

 True || False ⇒ True True && False ⇒ False True == False ⇒ False True /= False ⇒ True (/=)    
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

べき乗

 x^n   n (Int  Integer) x**y    y ( Float)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Integer



は、マシンのRAMを除き、サイズの制限はありません。

 4^103 102844034832575377634685573909834406561420991602098741459288064
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そうそう！

そして、有理数を使用できます！

ただし、このためにはData.Ratio



モジュールを使用する必要があります。

 $ ghci .... Prelude> :m Data.Ratio Data.Ratio> (11 % 15) * (5 % 3) 11 % 9
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

リスト

 [] ⇔   [1,2,3] ⇔    ["foo","bar","baz"] ⇔   (String) 1:[2,3] ⇔ [1,2,3], (:)    1:2:[] ⇔ [1,2] [1,2] ++ [3,4] ⇔ [1,2,3,4], (++)   [1,2,3] ++ ["foo"] ⇔  String ≠ Integral [1..4] ⇔ [1,2,3,4] [1,3..10] ⇔ [1,3,5,7,9] [2,3,5,7,11..100] ⇔ !    ! [10,9..1] ⇔ [10,9,8,7,6,5,4,3,2,1]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

行

Haskellでは、文字列はChar



リストです。

 'a' :: Char "a" :: [Char] "" ⇔ [] "ab" ⇔ ['a','b'] ⇔ 'a':"b" ⇔ 'a':['b'] ⇔ 'a':'b':[] "abc" ⇔ "ab"++"c"
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

注 ：

実際のタスクでは、文字のリストを使用してテキストを操作しません。

ほとんどの場合、 Data.Text



これに使用されます。

ASCII文字のストリームを操作する必要がある場合は、 Data.ByteString



を使用する必要があります。

タプル

次のようにペアを指定できます(a,b)



。

タプルの要素にはさまざまなタイプがあります。

 --    -  (2,"foo") (3,'a',[2,3]) ((2,"a"),"c",3) fst (x,y) ⇒ x snd (x,y) ⇒ y fst (x,y,z) ⇒ ERROR: fst :: (a,b) -> a snd (x,y,z) ⇒ ERROR: snd :: (a,b) -> b
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

括弧を扱います

余分な角かっこを取り除くには、これらの関数($)



と(.)



使用できます。

 --  : fghx ⇔ (((fg) h) x) -- $    $ --    fg $ hx ⇔ fg (hx) ⇔ (fg) (hx) f $ ghx ⇔ f (ghx) ⇔ f ((gh) x) f $ g $ hx ⇔ f (g (hx)) -- (.)   (f . g) x ⇔ f (gx) (f . g . h) x ⇔ f (g (hx))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

---

01_basic / 20_Essential_Haskell / 10a_Functions.lhs

関数を書くのに役立つこと

ちょっとした注意：

 x :: Int ⇔ x   Int x :: a ⇔ x     x :: Num a => a ⇔ x     a,     Num f :: a -> b ⇔ f      a     b f :: a -> b -> c ⇔ f  ,    a   (b→c) f :: (a -> b) -> c ⇔ f  ,    (a→b)   c
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

定義する前に関数型を宣言するのはオプションです。

Haskell自体が最も一般的なタイプを推測します。

ただし、関数のタイプを指定するのは経験則です。



中置エントリ

 square :: Num a => a -> a square x = x^2
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

^



中置記法で使用されることに注意してください。

各中置演算子には、接頭辞を書く可能性があります。

目的の演算子を角かっこで囲むだけです。

 square' x = (^) x 2 square'' x = (^2) x
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

式の左側と右側からx



を削除できます！

これは、η削減と呼ばれます。

 square''' = (^2)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

関数名に'



文字を使用できることに注意してください。

例：

square



⇔ square'



⇔ square''



⇔ square '''

テスト

 absolute :: (Ord a, Num a) => a -> a absolute x = if x >= 0 then x else -x
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

注：Haskellのif .. then .. else



は、演算子に似ています

¤?¤:¤



C. else



は省略できませelse



。



他の同等の機能：

 absolute' x | x >= 0 = x | otherwise = -x
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

注：Haskellプログラムではアライメントが重要です。

Pythonの場合と同様に、ミスアライメントはコードを破壊する可能性があります！

難しい部分

複雑な部分の研究に進みます。

機能的なスタイル

このセクションでは、Haskellの驚くべきコードリファクタリング機能の小さな例を紹介します。

問題を選択し、標準の命令的な方法で解決します。 次に、このコードを少し改善し始めます。 最終結果は、はるかに理解しやすく、よりエレガントになります。





解決する問題の状態は次のとおりです。

整数のリストがある場合、リスト内の偶数の合計を計算する必要があります。



例：

[1,2,3,4,5] ⇒ 2 + 4 ⇒ 6

機能的アプローチと命令型アプローチの違いを示すために、最初に命令型ソリューションを（Javascriptで）記述します。

 function evenSum(list) { var result = 0; for (var i=0; i< list.length ; i++) { if (list[i] % 2 ==0) { result += list[i]; } } return result; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

しかし、Haskellには変数とループはありません。

ループを使用しなくても、再帰を使用して同じ結果を得ることができます。

注 ：

命令型言語の再帰は、遅いツールであるという評判があります。 しかし、ほとんどの機能言語ではそうではありません。 ほとんどの場合、Haskellは非常に高品質で再帰関数を使用して作業を最適化します。

C



記述された再帰関数のバージョンを次に示しますC



簡単にするために、数字のリストがヌル値で終わると仮定します。

 int evenSum(int *list) { return accumSum(0,list); } int accumSum(int n, int *list) { int x; int *xs; if (*list == 0) { // if the list is empty return n; } else { x = list[0]; // let x be the first element of the list xs = list+1; // let xs be the list without x if ( 0 == (x%2) ) { // if x is even return accumSum(n+x, xs); } else { return accumSum(n, xs); } } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このコードをよく見てください。 Haskellに翻訳するからです。

しかし、最初に、使用する3つのシンプルだが非常に便利な関数を紹介します。

 even :: Integral a => a -> Bool head :: [a] -> a tail :: [a] -> [a]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

even



パリティチェック。

 even :: Integral a => a -> Bool even 3 ⇒ False even 2 ⇒ True
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

head



はリストの最初の要素を返します：

 head :: [a] -> a head [1,2,3] ⇒ 1 head [] ⇒ ERROR
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

tail



は、最初のリストに加えて、リストのすべての要素を返します。

 tail :: [a] -> [a] tail [1,2,3] ⇒ [2,3] tail [3] ⇒ [] tail [] ⇒ ERROR
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

空でないリストl



、

l ⇔ (head l):(tail l)

---

02_Hard_Part / 11_Functions.lhs



だから、Haskellの問題に対する最初の解決策。

evenSum



関数は、リスト内のすべての偶数の合計を返します。

 --  1 evenSum :: [Integer] -> Integer evenSum l = accumSum 0 l accumSum nl = if l == [] then n else let x = head l xs = tail l in if even x then accumSum (n+x) xs else accumSum n xs
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

関数をテストするには、 ghci



実行するだけghci



：

 % ghci GHCi, version 7.0.3: http://www.haskell.org/ghc/ :? for help Loading package ghc-prim ... linking ... done. Loading package integer-gmp ... linking ... done. Loading package base ... linking ... done. Prelude> :load 11_Functions.lhs [1 of 1] Compiling Main ( 11_Functions.lhs, interpreted ) Ok, modules loaded: Main. *Main> evenSum [1..5] 6
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

以下は、関数がどのように機能するかの例です（私はごまかしています。知っています。後でルーズコンピューティングの問題に戻ります）。

 *Main> evenSum [1..5] accumSum 0 [1,2,3,4,5] 1 is odd accumSum 0 [2,3,4,5] 2 is even accumSum (0+2) [3,4,5] 3 is odd accumSum (0+2) [4,5] 4 is even accumSum (0+2+4) [5] 5 is odd accumSum (0+2+4) [] l == [] 0+2+4 0+6 6
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

命令型言語の観点からは、すべてが正常に見えます。 しかし、改善の余地はたくさんあります。 手始めに、型をより一般的にすることができます。

 evenSum :: Integral a => [a] -> a
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

02_Hard_Part / 11_Functions.lhs

---

02_Hard_Part / 12_Functions.lhs



次のステップは、 where



またはlet



定義されたネストされた関数を使用するlet



です。

したがって、 accumSum



関数accumSum



グローバル名前空間を汚染しません。

 --  2 evenSum :: Integral a => [a] -> a evenSum l = accumSum 0 l where accumSum nl = if l == [] then n else let x = head l xs = tail l in if even x then accumSum (n+x) xs else accumSum n xs
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

02_Hard_Part / 12_Functions.lhs

---

02_Hard_Part / 13_Functions.lhs



次に、パターンマッチングを使用します。

 --  3 evenSum l = accumSum 0 l where accumSum n [] = n accumSum n (x:xs) = if even x then accumSum (n+x) xs else accumSum n xs
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

パターンマッチングとは 名前付きパラメーターの代わりに値を使用するだけです。 （最も大胆な場合は、パターンマッチングの詳細な説明をここで調べることができます ）



このコードの代わりに： foo l = if l == [] then <x> else <y>





あなたは簡単に書くことができます：

 foo [] = <x> foo l = <y>
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ただし、サンプルとの比較ではさらに多くのことができます。 複雑な構造の内部データを分析できます。 交換できます

 foo l = let x = head l xs = tail l in if even x then foo (n+x) xs else foo n xs
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

に

 foo (x:xs) = if even x then foo (n+x) xs else foo n xs
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

非常に便利な機能。

これにより、コードがより簡潔で読みやすくなります。



02_Hard_Part / 13_Functions.lhs

---

02_Hard_Part / 14_Functions.lhs



η-reductionを使用すると、Haskellで関数の記述を簡単にできます。

たとえば、そのようなエントリの代わりに：

 fx = (- ) x
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

使用できます

 f = - 
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このアプローチを使用してl



を取り除くことができます。

 --  4 evenSum :: Integral a => [a] -> a evenSum = accumSum 0 where accumSum n [] = n accumSum n (x:xs) = if even x then accumSum (n+x) xs else accumSum n xs
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

02_Hard_Part / 14_Functions.lhs

---

02_Hard_Part / 15_Functions.lhs

高階関数

関数をさらに美しくするために、FEP（高階関数）を使用できます。

どのような動物を尋ねますか？

高階関数は、関数をパラメーターとしてとる関数です。



いくつかの例：

 filter :: (a -> Bool) -> [a] -> [a] map :: (a -> b) -> [a] -> [b] foldl :: (a -> b -> a) -> a -> [b] -> a
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

私たちは少しずつ前進します。

 --  5 evenSum l = mysum 0 (filter even l) where mysum n [] = n mysum n (x:xs) = mysum (n+x) xs
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

どこで

 filter even [1..10] ⇔ [2,4,6,8,10]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

filter



関数は、引数として型（ a -> Bool



）の関数と型[a]



リストを取ります。 関数がtrue



を返した要素のみを含むリストを返しtrue



。



次のステップは、サイクルをさらに簡素化することです。 値を累積できるfoldl



関数を使用します。 foldl



関数は、一般的なプログラミング手法を実装します。

 myfunc list = foo initialValue list foo accumulated [] = accumulated foo tmpValue (x:xs) = foo (bar tmpValue x) xs
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

上記のコードは次のものに置き換えることができます。

 myfunc list = foldl bar initialValue list
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

あなたが本当に魔法が起こっているかを理解したい場合は、

foldl



実装foldl



以下に示します。

 foldl fz [] = z foldl fz (x:xs) = foldl f (fzx) xs
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

 foldl fz [x1,...xn] ⇔ f (... (f (fz x1) x2) ...) xn
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

しかし、Haskellは遅延言語であるため、値(fzx)



計算せず(fzx)



スタックにプッシュします。

したがって、 foldl'



代わりにfoldl



foldl'



を使用します。

foldl'



は、 厳密な（または精力的な） foldl



実装です。



遅延関数と厳密関数の違いが明らかでない場合は、両方の関数が同じであることを考慮して、コードを読んでください。





これで、 evenSum



バージョンは次のようになります。

 --  6 -- foldl'     --       Data.List import Data.List evenSum l = foldl' mysum 0 (filter even l) where mysum acc value = acc + value
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このコードは、ラムダ式を使用することでさらに簡単になり、一時的なmysum



識別子をmysum



ます。

 --  7 --     --     import Data.List (foldl') evenSum l = foldl' (\xy -> x+y) 0 (filter even l)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そしてもちろん、次の交換を行うことができます

 (\xy -> x+y) ⇔ (+)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

02_Hard_Part / 15_Functions.lhs

---

02_Hard_Part / 16_Functions.lhs



最後に

 --  8 import Data.List (foldl') evenSum :: Integral a => [a] -> a evenSum l = foldl' (+) 0 (filter even l)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

foldl'



最も直感的な機能ではありません。しかし、それは間違いなく対処する価値があります。



これを行うために、段階的な分析を実行します。

 evenSum [1,2,3,4] ⇒ foldl' (+) 0 (filter even [1,2,3,4]) ⇒ foldl' (+) 0 [2,4] ⇒ foldl' (+) (0+2) [4] ⇒ foldl' (+) 2 [4] ⇒ foldl' (+) (2+4) [] ⇒ foldl' (+) 6 [] ⇒ 6
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

別の有用な高階関数はこれ(.)



です。

この関数(.)



は、数学的な構成に対応しています。

 (f . g . h) x ⇔ f ( g (hx))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これを使用して、関数をさらにη削減できます。

 --  9 import Data.List (foldl') evenSum :: Integral a => [a] -> a evenSum = (foldl' (+) 0) . (filter even)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

コードをきれいにするために何か他のことができます：

 --  10 import Data.List (foldl') sum' :: (Num a) => [a] -> a sum' = foldl' (+) 0 evenSum :: Integral a => [a] -> a evenSum = sum' . (filter even)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

結果について議論します。

高階関数を適用することで何が得られましたか？



コードの簡潔さが目を引きます。しかし、主なプラスは、プログラムを理解することがどれほど簡単になったかです。関数を少し変更したいとしましょう。ここで、リスト内のすべての偶数の平方和を返すように彼女に求めています。

 [1,2,3,4] ▷ [1,4,9,16] ▷ [4,16] ▷ 20
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この変更をバージョン10に追加するのは非常に簡単です。

 squareEvenSum = sum' . (filter even) . (map (^2)) squareEvenSum' = evenSum . (map (^2)) squareEvenSum'' = sum' . (map (^2)) . (filter even)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

別の「変換関数」を追加するだけです（squareEvenSum''



他の2つの実装よりも効率的であることに注意してください。順序は(.)



本当に重要です）。

 map (^2) [1,2,3,4] ⇔ [1,4,9,16]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この関数map



は、パラメーター関数をリストのすべての要素に適用するだけです。関数定義内で



何かを変更する必要はありません。はるかにモジュール化されています。しかし、とりわけ、彼女はより「数学的に」振る舞い始めました。他の関数と同じように関数を使用できます。新しい機能を使用して、構成、マップ、折り畳み、およびフィルターを実行できます。1つのバージョンのリファクタリングをタスクとして読者に任せます。たとえば、この関数はリストだけでなく再帰型にも使用できます。方法に興味がある場合-この楽しい記事を読んでください：















Meijer、Fokkinga、Patersonによるバナナ、レンズ、エンベロープ、有刺鉄線による関数型プログラミング。



この例では、関数型プログラミングがどれほど強力であるかがわかります。残念ながら、場合によっては、純粋に機能的な言語が常に最良の選択とは限りません。少なくとも、真に普遍的な関数型言語はまだ作成されていません。



Haskellの際立った特徴の1つは、DSL（ドメイン指向言語）の作成にあります。





実際、命令型のプログラムを作成したい場合でも、Haskellは優れたツールです。Haskellを研究したとき、この考えは私にとって啓示でした。





しかし、Haskellの超大国について話をする前に、もう1つの重要な側面- タイプ 。

種類

tl; dr：

• type Name = AnotherType
  
  
  
  それは単に、コンパイラの種類の別名であるName
  
  
  
  とAnotherType
  
  
  
  同じように見えます。
• data Name = NameConstructor AnotherType
  
  
  
  この例では、タイプが異なります。
• data
  
  
  
  再帰構造を作成できます。
• deriving
  
  
  
  それは強力な魔術であり、あなたのための機能を作成できます。

Haskellは、強力な静的型付けを備えた言語です。



なぜこれがそんなに重要なのですか？エラーの数を大幅に減らすためです。

Haskellでは、ほとんどのエラーはコンパイル段階で検出できます。これは、コンパイル中に型のコンパイルが積極的に使用されるために発生します。

間違った場所で間違ったパラメーターを使用すると、コンパイラーは簡単にこれに気付くでしょう。

型推論

高速プログラムを作成するには静的型付けが必要ですが

、ほとんどの静的型付け言語は概念を一般化するのに弱いです。



Haskellの優れた能力の1つは型推論です。



簡単な例。

square



Haskell 関数：

 square x = x * x
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この関数はsquare



、数値型の任意の値を（平方）できます。

あなたはに値型を渡すことができInt



、Integer



、Float



、Fractional



とさえComplex



。例：

 % ghci GHCi, version 7.0.4: ... Prelude> let square x = x*x Prelude> square 2 4 Prelude> square 2.1 4.41 Prelude> --   Data.Complex Prelude> :m Data.Complex Prelude Data.Complex> square (2 :+ 1) 3.0 :+ 4.0
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

x :+ y



これは、複素数（x + iy）の表記です。



次に、Cプログラムと比較したコードの量を比較します。

 int int_square(int x) { return x*x; } float float_square(float x) {return x*x; } complex complex_square (complex z) { complex tmp; tmp.real = z.real * z.real - z.img * z.img; tmp.img = 2 * z.img * z.real; } complex x,y; y = complex_square(x);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

タイプごとに、独自の関数を作成する必要があります。これを回避するには、メタプログラミング手法を使用する必要があります。たとえば、プリプロセッサを使用します。C ++は、テンプレートを使用したより美しいソリューションを提供します。

 #include <iostream> #include <complex> using namespace std; template<typename T> T square(T x) { return x*x; } int main() { // int int sqr_of_five = square(5); cout << sqr_of_five << endl; // double cout << (double)square(5.3) << endl; // complex cout << square( complex<double>(5,3) ) << endl; return 0; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

C ++バリアントはCよりも格段に優れています。

しかし、複雑な変数の関数の場合、同じ構文を維持することは困難です。この記事の例を

ご覧ください。

。



C ++では、さまざまな型で機能する関数を記述する必要があります。

Haskellでは、状況は逆です。

関数はデフォルトで可能な限り一般化されます。



Haskell型推論は、動的に型付けされた言語が表す自由感を与えます。

しかし、動的に型付けされた言語とは異なり、ほとんどのエラーはプログラムが実行される前でもキャッチされます。

人々はこのようにHaskellについて話します：

「コンパイルされた場合、ほとんどの場合正しく動作します」

---

02_Hard_Part / 21_Types.lhs

新しいタイプの作成

独自のタイプを作成できます。たとえば、型シノニムを宣言できます。

 type Name = String type Color = String showInfos :: Name -> Color -> String showInfos name color = "Name: " ++ name ++ ", Color: " ++ color name :: Name name = "Robin" color :: Color color = "Blue" main = putStrLn $ showInfos name color
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

しかし、これは間違いからあなたを保護するものではありません。

関数の2つのパラメーターを交換してshowInfos



、プログラムを実行してみてください。

 putStrLn $ showInfos color name
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

コンパイルして実行します。Name、Color、およびStringを交換可能なエンティティとして使用できます。コンパイラーにとっては、まったく同じです。

独自のタイプを作成する別の方法は、キーワードを使用することdata



です。

 data Name = NameConstr String data Color = ColorConstr String showInfos :: Name -> Color -> String showInfos (NameConstr name) (ColorConstr color) = "Name: " ++ name ++ ", Color: " ++ color name = NameConstr "Robin" color = ColorConstr "Blue" main = putStrLn $ showInfos name color
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

showInfos



パラメーターを交換すると、コンパイラーは誓い始めます。間違いを犯す機会はなくなりました。ただし、コードの量を増やすことは犠牲になります。



型コンストラクタは関数であることに注意してください。

 NameConstr :: String -> Name ColorConstr :: String -> Color
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

data



通常、使用方法は次のようになります。

 data TypeName = ConstructorName [types] | ConstructorName2 [types] | ...
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

のために

DataTypeNameとDataTypeConstructorは通常同じ名前を使用します。

例：

 data Complex = Num a => Complex aa
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

エントリの構文を使用することもできます。

 data DataTypeName = DataConstructor { field1 :: [type of field1] , field2 :: [type of field2] ... , fieldn :: [type of fieldn] }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

また、多数のデータアクセス関数が自動的に作成されます。さらに、新しい値を書き込むとき、任意の順序のフィールドを使用できます。



例：

 data Complex = Num a => Complex { real :: a, img :: a} c = Complex 1.0 2.0 z = Complex { real = 3, img = 4 } real c ⇒ 1.0 img z ⇒ 4
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

02_Hard_Part / 22_Types.lhs

---

02_Hard_Part / 23_Types.lhs

再帰型

リストを使用して、再帰型の代表者と既に会っています。より詳細な構文を使用して、リストを最初から作成できます。

 data List a = Empty | Cons a (List a)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

記録を簡単にするために、中置型コンストラクターを使用できます。

 infixr 5 ::: data List a = Nil | a ::: (List a)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

後の数字infixr



は、オペレーターの優先順位です。新しいタイプの値



を印刷（Show



）、読み取り（Read



）、チェック（Eq



）、比較（Ord



）する場合、必要な関数を自動的に印刷するようにHaskellに指示できます。

 infixr 5 ::: data List a = Nil | a ::: (List a) deriving (Show,Read,Eq,Ord)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

deriving (Show)



タイプの説明に追加すると、Haskellは自動的に関数を作成しますshow



。すぐにあなたの関数のバージョンを書く方法を見るでしょうshow



。

 convertList [] = Nil convertList (x:xs) = x ::: convertList xs
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

 main = do print (0 ::: 1 ::: Nil) print (convertList [0,1])
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

プログラム出力：

 0 ::: (1 ::: Nil) 0 ::: (1 ::: Nil)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

02_Hard_Part / 23_Types.lhs

---

02_Hard_Part / 30_Trees.lhs

木々

もう1つの標準的な例を次に示します。バイナリツリー。

 import Data.List data BinTree a = Empty | Node a (BinTree a) (BinTree a) deriving (Show)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

リストを順序付き二分木に変換する関数を書きましょう。

 treeFromList :: (Ord a) => [a] -> BinTree a treeFromList [] = Empty treeFromList (x:xs) = Node x (treeFromList (filter (<x) xs)) (treeFromList (filter (>x) xs))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この機能の優雅さをお楽しみください。

ロシア語への翻訳：

• 空のリストは空のツリーに変わります。
• リスト(x:xs)
  
  
  
  は次のようなツリーになります。
  
  
  • ルートは x
    
    
    
    
  • 左のサブツリーがリストに作成され、xs
    
    
    
    厳密に小さく、x
    
    
    
    かつ
  • xs
    
    
    
    厳密に大きいリスト要素から正しいサブツリーが作成されx
    
    
    
    ます。
  
  
  

 main = print $ treeFromList [7,2,4,8]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

次のようなものが得られるはずです。

 Node 7 (Node 2 Empty (Node 4 Empty Empty)) (Node 8 Empty Empty)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これは有益ですが、私たちのツリーをあまり美しく表現していません。



02_Hard_Part / 30_Trees.lhs

---

02_Hard_Part / 31_Trees.lhs



楽しい時間を過ごすために、ツリーをより美しく表示するためのコードを書きましょう。どんな木でもうまく表示できる関数を書くのは本当に楽しかったです。この部分が難しいと思われる場合は、安全にスキップできます。



小さな変更を加える必要があります。型宣言から

削除deriving (Show)



しBinTree



ます。 BinTreeを型クラス（Eq



およびOrd



）のインスタンスにすることも役立ちます。これにより、ツリーの等価性をテストし、比較する機会が得られます。

 data BinTree a = Empty | Node a (BinTree a) (BinTree a) deriving (Eq,Ord)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

なしではderiving (Show)



、Haskellは私たちのためのメソッドを作成しませんshow



。

ただし、独自のバージョンを作成しますshow



。これを行うにBinTree a





は、新しく作成された型が型classのインスタンスであることを示す必要がありますShow



。

コードでは、次のようになります。

 instance Show (BinTree a) where show t = ... --     
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここに、バイナリツリーを表示する私のバージョンがあります。見た目ほど怖くないので、もっと奇妙なオブジェクトを表示するように調整しました。

 --   BinTree   Show instance (Show a) => Show (BinTree a) where --     '<' --   :    show t = "< " ++ replace '\n' "\n: " (treeshow "" t) where -- treeshow pref Tree --        pref --       treeshow pref Empty = "" -- Leaf treeshow pref (Node x Empty Empty) = (pshow pref x) --    treeshow pref (Node x left Empty) = (pshow pref x) ++ "\n" ++ (showSon pref "`--" " " left) --    treeshow pref (Node x Empty right) = (pshow pref x) ++ "\n" ++ (showSon pref "`--" " " right) --        treeshow pref (Node x left right) = (pshow pref x) ++ "\n" ++ (showSon pref "|--" "| " left) ++ "\n" ++ (showSon pref "`--" " " right) --      showSon pref before next t = pref ++ before ++ treeshow (pref ++ next) t -- pshow  "\n"  "\n"++pref pshow pref x = replace '\n' ("\n"++pref) (show x) --    replace c new string = concatMap (change c new) string where change c new x | x == c = new | otherwise = x:[] -- "x"
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

メソッドtreeFromList



は変更されません。

 treeFromList :: (Ord a) => [a] -> BinTree a treeFromList [] = Empty treeFromList (x:xs) = Node x (treeFromList (filter (<x) xs)) (treeFromList (filter (>x) xs))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そして今、私たちは遊ぶことができます：

 main = do putStrLn "Int binary tree:" print $ treeFromList [7,2,4,8,1,3,6,21,12,23]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

 print $ treeFromList [7,2,4,8,1,3,6,21,12,23] Int binary tree: < 7 : |--2 : | |--1 : | `--4 : | |--3 : | `--6 : `--8 : `--21 : |--12 : `--23
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

はるかに良い！ツリーのルートは、シンボルとともに表示されます<



。そして、後続の各行はで始まります:



。

ただし、別のタイプを使用できます。

 putStrLn "\nString binary tree:" print $ treeFromList ["foo","bar","baz","gor","yog"]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

 String binary tree: < "foo" : |--"bar" : | `--"baz" : `--"gor" : `--"yog"
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

また、ツリーの等価性をテストして順序を設定できるため、ツリーツリーを作成できます。

 putStrLn "\n      :" print ( treeFromList (map treeFromList ["baz","zara","bar"]))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

       : < < 'b' : : |--'a' : : `--'z' : |--< 'b' : | : |--'a' : | : `--'r' : `--< 'z' : : `--'a' : : `--'r'
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これが、各新しい行のプレフィックスとして（ルートを除く）を選択した理由:



です。

 putStrLn "\nTree of Binary trees of Char binary trees:" print $ (treeFromList . map (treeFromList . map treeFromList)) [ ["YO","DAWG"] , ["I","HEARD"] , ["I","HEARD"] , ["YOU","LIKE","TREES"] ]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これは以下と同等です：

 print ( treeFromList ( map treeFromList [ map treeFromList ["YO","DAWG"] , map treeFromList ["I","HEARD"] , map treeFromList ["I","HEARD"] , map treeFromList ["YOU","LIKE","TREES"] ]))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

結果として：

 Binary tree of Binary trees of Char binary trees: < < < 'Y' : : : `--'O' : : `--< 'D' : : : |--'A' : : : `--'W' : : : `--'G' : |--< < 'I' : | : `--< 'H' : | : : |--'E' : | : : | `--'A' : | : : | `--'D' : | : : `--'R' : `--< < 'Y' : : : `--'O' : : : `--'U' : : `--< 'L' : : : `--'I' : : : |--'E' : : : `--'K' : : `--< 'T' : : : `--'R' : : : |--'E' : : : `--'S'
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

重複は挿入されないことに注意してください。

対応する1つのツリーのみが表示されます"I","HEARD"



。Treeをインスタンスと宣言したため、この機会は（ほぼ）無料で得られましたEq



。



このタイプの美しさと力を見てください。数字、線、記号だけでなく、他のツリーで構成されるツリーを作成できます。要素がツリーツリーであるツリーを作成することもできます！





02_Hard_Part / 31_Trees.lhs

---

02_Hard_Part / 40_Infinites_Structures.lhs

無限の構造

Haskellはしばしば怠zyな言語と呼ばれます。



しかし、Haskellは厳密な言語ではないと言うのは正しいことです。怠azineは、厳密ではない言語の一般的な実装です。



緩い言語とは何ですか？Haskell-wikiから：

リダクション（式を計算するための数学用語）は、外側から内側に進みます。



式がある場合は、(a+(b*c))



最初+



に評価し、次に内部式(b*c)

たとえば、Haskellを使用すると、次のことができます。

 -- numbers = [1,2,..] numbers :: [Integer] numbers = 0:map (1+) numbers take' n [] = [] take' 0 l = [] take' n (x:xs) = x:take' (n-1) xs main = print $ take' 10 numbers
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そして、プログラムは終了します。



どうやって？



すべてを計算する代わりに



、必要な要素のみを計算します。



Haskellで無限リストを指定する構文に注意してください

 [1..] ⇔ [1,2,3,4...] [1,3..] ⇔ [1,3,5,7,9,11...]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そして、ほとんどの機能はそのようなリストを扱うことができます。take



私たちのものと同一の標準機能さえありtake'



ます。



02_Hard_Part / 40_Infinites_Structures.lhs

---

02_Hard_Part / 41_Infinites_Structures.lhs



順序付けられた二分木を持つことを気にしないとしましょう。無限バイナリツリーの例を次に示します。

 nullTree = Node 0 nullTree nullTree
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

各ノードにゼロがある完全な二分木。次の関数を使用してこのツリーを操作できることを証明します。

 --    BinTree --      treeTakeDepth _ Empty = Empty treeTakeDepth 0 _ = Empty treeTakeDepth n (Node x left right) = let nl = treeTakeDepth (n-1) left nr = treeTakeDepth (n-1) right in Node x nl nr
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このプログラムが出力するものを見てみましょう：

 main = print $ treeTakeDepth 4 nullTree
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このコードは、次の結果をコンパイル、開始、停止、表示します。

 < 0 : |-- 0 : | |-- 0 : | | |-- 0 : | | `-- 0 : | `-- 0 : | |-- 0 : | `-- 0 : `-- 0 : |-- 0 : | |-- 0 : | `-- 0 : `-- 0 : |-- 0 : `-- 0
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ニューロンを少し揺らすには、ツリーをより奇妙にします。

 iTree = Node 0 (dec iTree) (inc iTree) where dec (Node xlr) = Node (x-1) (dec l) (dec r) inc (Node xlr) = Node (x+1) (inc l) (inc r)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

同様のツリーは、高次関数を使用して作成することもできます。

この関数はに似てmap



いBinTree



ますが、リストの代わりに機能するはずです。

このような関数の可能な実装の1つを次に示します。

 --      Tree treeMap :: (a -> b) -> BinTree a -> BinTree b treeMap f Empty = Empty treeMap f (Node x left right) = Node (fx) (treeMap f left) (treeMap f right)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ヒント：このトピックにこだわることはもうありません。あなたが一般化を見て好奇心旺盛であればmap



他のデータ構造に、キーワードファンクタ（ファンクタ）を検索しfmap



。



私たちの実装：

 infTreeTwo :: BinTree Int infTreeTwo = Node 0 (treeMap (\x -> x-1) infTreeTwo) (treeMap (\x -> x+1) infTreeTwo)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そして、実行の結果

 main = print $ treeTakeDepth 4 infTreeTwo
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

 < 0 : |-- -1 : | |-- -2 : | | |-- -3 : | | `-- -1 : | `-- 0 : | |-- -1 : | `-- 1 : `-- 1 : |-- 0 : | |-- -1 : | `-- 1 : `-- 2 : |-- 1 : `-- 3
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

02_Hard_Part / 41_Infinites_Structures.lhs