TRANSLATIONの2番目の部分は、Haskellの短くて難しい紹介です。 最初のものはここから入手できます。
オリジナルはこちら
くそハード部分
おめでとうございます! あなたは本当に遠くに行きました。
そして今、ゴミ、廃棄物、ソドミーが始まります:)。
あなたと私が似ているなら、あなたはすでに機能的なスタイルに少し動いています。 あなたは怠lazがデフォルトで与える利点を理解しています。 しかし、あなたは本当にあなたが本当に有用なプログラムを書くことができる方法をまだよく理解していません。 特に:
- 副作用をどうするか?
- 入出力(IO)を操作するために、なぜこのような奇妙な構文が必要なのですか?
準備をしてください、答えは最も単純ではないかもしれません。
しかし、その利点は否定できません。
03_地獄/ 01_IO / 01_progressive_io_example.lhs
IOを扱う
tl; dr :
IO
で動作する典型的な関数は、命令型プログラムのように見えます。
f :: IO a f = do x <- action1 action2 x y <- action3 action4 xy
- オブジェクトに値を割り当てるには、
<-
を使用します。- この例では、各行の式のタイプは
IO *
です。
action1 :: IO b
action2 x :: IO ()
action3 :: IO c
action4 xy :: IO a
x :: b
、y :: c
- いくつかのオブジェクトは
IO a
型です。
このようなオブジェクトでは、純粋な関数を使用できません。
純粋な関数を使用するには、action2 (purefunction x)
を実行する必要があります。
このセクションでは、IOの使用方法を示しますが、動作方法は示しません。
Haskellがプログラムのクリーンな部分と副作用のある部分をどのように分離するかがわかります。
構文の詳細が少し理解できない場合でも、停止しないでください。
次のセクションでそれらに戻ります。
何を取得したいですか?
ユーザーから番号のリストを取得します。 金額を印刷する
toList :: String -> [Integer] toList input = read ("[" ++ input ++ "]") main = do putStrLn " ( ):" input <- getLine print $ sum (toList input)
このプログラムの動作は明らかです。
しかし、型を詳しく見てみましょう。
putStrLn :: String -> IO () getLine :: IO String print :: Show a => a -> IO ()
do
ブロック内のすべての式が
IO a
型であることに気づきまし
IO a
か?
main = do putStrLn " ... " :: IO () getLine :: IO String print Something :: IO ()
<-
文字の動作にも注意してください。
do x <- something
something :: IO a
場合、
x :: a
。
IO
使用に関する重要な注意。 doブロック内のすべての行は、次の2つの方法のいずれかで見る必要があります。
action1 :: IO a -- a = ()
または
value <- action2 -- -- bar zt :: IO b -- value :: b
これらの2つのエントリは、アクションを記述するさまざまな方法に対応しています。 次のセクションの終わりまでに、この提案に完全に気付くでしょう。
03_地獄/ 01_IO / 01_progressive_io_example.lhs
03_地獄/ 01_IO / 02_progressive_io_example.lhs
このプログラムの動作を見てみましょう、たとえば、ユーザーが何か奇妙なものを入力した場合はどうなりますか?
私達は試みます:
% runghc 02_progressive_io_example.lhs Enter a list of numbers (separated by comma): foo Prelude.read: no parse
ああ! 悪魔のようなエラーメッセージとプログラムのクラッシュ!
次に、エラーメッセージが読みやすいように、最初のステップを実行する必要があります。
これを行うには、何かがうまくいかなかったことを理解する必要があります。
1つの方法は、
Maybe
タイプを使用することです。
このタイプはHaskellプログラムで非常によく使用されます。
import Data.Maybe
これは何ですか?
Maybe
これは1つのパラメータを取るタイプです。 彼の定義は次のとおりです。
data Maybe a = Nothing | Just a
これは、値を作成または計算しようとしてエラーが発生したかどうかを理解するための良い方法です。
maybeRead
関数は、このアプローチの優れた例です。
この関数は、
read
関数(JSON文字列を処理するjavascript関数
eval
に非常に似ています)に似ています。
しかし、何かがうまくいかない場合、結果は
Nothing
ます。
結果が正しい場合、
Just <>
を返し
Just <>
。
この機能を深く掘り下げないでください。
その中のコードは
read
よりも低いです。 。
maybeRead :: Read a => String -> Maybe a maybeRead s = case reads s of [(x,"")] -> Just x _ -> Nothing
コードが読みやすくなったので、次の機能を作成します。
文字列の形式が間違っていた場合、
Nothing
を返します。
他の場合、たとえば「1,2,3」の場合、
Just [1,2,3]
を返します。
getListFromString :: String -> Maybe [Integer] getListFromString str = maybeRead $ "[" ++ str ++ "]"
次に、main関数を使用してコードをテストします。
main :: IO () main = do putStrLn " , :" input <- getLine let maybeList = getListFromString input in case maybeList of Just l -> print (sum l) Nothing -> error " . ."
エラーが発生した場合、素晴らしいエラーメッセージが表示されます。
この場合、メイン関数のdoブロック内の各式のタイプは
IO a
ままです。
唯一の奇妙なことは
error
です。
error msg
関数は、あらゆるタイプの入力(この場合は
IO ()
を単純に受け入れます。
非常に重要なことに注意してください-すべての関数のタイプは事前定義されています。
タイプ
IO
とこれを持つ関数は、
main
です。
これは、mainが純粋な関数ではないことを意味します。
ただし、純粋な
getListFromString
関数を使用します。
宣言された関数型を見るだけで、純粋な関数と副作用のある関数を区別できます。
なぜ純粋な機能が重要なのですか?
いくつかのことを忘れることができますが、主な理由は3つあります。
- クリーンなコードは解析がはるかに簡単です。
- 清潔さは、副作用に関連する複雑で再現可能なエラーからあなたを守ります。
- 純粋な関数は、任意の順序で、またはリスクなしで並列に計算できます。
これらの理由により、クリーンな関数ではできるだけ多くのコードを保持する必要があります。
03_地獄/ 01_IO / 02_progressive_io_example.lhs
03_地獄/ 01_IO / 03_progressive_io_example.lhs
次のステップは、ユーザーが正しい答えを入力するまで常にユーザーをポーリングすることです。
最初の部分は変更されません。
import Data.Maybe maybeRead :: Read a => String -> Maybe a maybeRead s = case reads s of [(x,"")] -> Just x _ -> Nothing getListFromString :: String -> Maybe [Integer] getListFromString str = maybeRead $ "[" ++ str ++ "]"
そして、数字のリストを要求する関数を作成し、入力された有効なリストを受け取るまで終了しません。
askUser :: IO [Integer] askUser = do putStrLn " , :" input <- getLine let maybeList = getListFromString input in case maybeList of Just l -> return l Nothing -> askUser
この関数のタイプは
IO [Integer]
です。
これは、IOアクションを使用して
[Integer]
ような結果を得たことを意味します。
一部の人々はそれをこのように説明します:
「これはIO
内の[Integer]
」
I / Oメカニズムの内部構造を理解したい場合は、次のセクションをお読みください。
しかし、実際には、単にIOを使用する場合は、単純なプログラムをいくつか作成し、型について考えることを忘れないでください。
その結果、メイン関数ははるかにシンプルになりました。
main :: IO () main = do list <- askUser print $ sum list
これで
IO
紹介は終わりです。 すべてが非常に速く進みました。 覚えておいてほしいことは次のとおりです。
-
do
ブロックでは、各式はIO a
型である必要があります。
可能な表現のセットはかなり限られています:
getLine
、print
、putStrLn
など - 純粋な機能を最大限に活用します。
- タイプ
IO a
は、タイプa
結果を返す後続のIO アクションを意味します。
アクションを表すためIO
タイプIO a
は関数のタイプです。
まだ興味がある場合は、次のセクションをお読みください。
少し練習すれば、
IO
を使用しても問題はありません。
演習 :
- すべての引数を要約するプログラムを作成します。 ヒント:
getArgs
関数を使用します。
03_地獄/ 01_IO / 03_progressive_io_example.lhs
IOトリックの説明
tl; dr :
純粋な機能を区別するために、
main
、世界の状態を変える関数として定義されます
main :: World -> World
このタイプの関数には、副作用があることが保証されています。 典型的なメイン関数を見てください:
main w0 = let (v1,w1) = action1 w0 in let (v2,w2) = action2 v1 w1 in let (v3,w3) = action3 v2 w2 in action4 v3 w3
この例には多くの時間値があります(w1
、w2
およびw3
)
次のステップにデータを転送するために使用されます。
bind
または(>>=)
関数を作成しています。bind
おかげでbind
名前付きの一時的な値は必要なくなりました。
main = action1 >>= action2 >>= action3 >>= action4
おまけ:Haskellには構文シュガーがあります:
main = do v1 <- action1 v2 <- action2 v1 v3 <- action3 v2 action4 v3
なぜこのような奇妙な構文が必要なのですか?
IO
のタイプは何ですか? これはすべて何らかの魔法のように見えますが。
しばらくの間、純粋な関数については忘れましょう。 副作用に焦点を当てる:
askUser :: IO [Integer] askUser = do putStrLn " , :" input <- getLine let maybeList = getListFromString input in case maybeList of Just l -> return l Nothing -> askUser main :: IO () main = do list <- askUser print $ sum list
まず、このコードはまるで通常の命令型言語で書かれているかのように見えます。
Haskellは、サイドアクションコードが不可欠に見えるほどクールです。
必要に応じて、Haskellで
while
アナログを作成できます。
実際には、
IO
で作業する場合、命令型のスタイルがより適しています。
しかし、あなたはおそらく録音がやや珍しいことに気づいたでしょう。 それで、理由の詳細な説明に行きました。
ほとんどの言語では、世界の状態は大きな暗黙のグローバル変数と考えることができます。 この暗黙的な変数は、プログラムのどこからでもアクセスできます。 たとえば、任意の関数でファイルから\を読み取ることができます。 一方、ファイルの有無は、世界のさまざまな状態と見なすことができます。
Haskellでは、世界の状態は明示的に設定されます。
main
機能が世界の状態を変える可能性があることを明確に述べています。 そして、そのタイプは次のようになります。
main :: World -> World
ただし、この変数はすべての機能で使用できるわけではありません。
この変数を使用する関数はクリーンではありません。
それを使用しない関数は純粋です(この規則には危険な例外があります。しかし、実際のプログラムでは、それは必要ありません。詳細なデバッグの場合を除きます)。
Haskellは、世界は
main
関数への入力パラメーターであると考えています。
しかし、この関数の実際の型は次のようなものです
main :: World -> ((),World)
(興味のある方は、式のタイプは
data IO a = IO {unIO :: State# RealWorld -> (# State# RealWorld, a #)}
です。すべての
#
は最適化に関連しており、この例ではいくつかのフィールドを入れ替えました。しかし、全体的には、考え方は変わっていません。)
タイプ
()
は空のタイプです。
空虚。
次のことを忘れずに、関数を書き直しましょう。
main w0 = let (list,w1) = askUser w0 in let (x,w2) = print (sum list,w1) in x
まず、副作用のあるすべての関数には特定の型が必要です。
World -> (a,World)
a
は結果のタイプです。
たとえば、
getChar
関数のタイプは
World -> (Char,World)
なければなりません。
別の非自明なことは、関数が計算される順序です。
Haskellでは、
fab
を計算しようとすると、いくつかのオプションがあります:
-
a
、b
、fab
順に計算a
fab
- 最初に
b
計算し、次にb
計算a
、最後にfab
計算しfab
。 -
a
とb
を並列に計算しa
からfab
言語は機能的に純粋であるため、このようなトリックは現実的です。
メイン関数をよく見ると、最初の行は2番目の行のパラメーターを計算する必要があるため、最初の行を2番目の行の前に計算する必要があることは明らかです。
このトリックはうまく機能します。
計算の各ステップで、コンパイラは新しい変更された世界へのポインタを渡します。
内部では、
print
は次のように機能します。
- 画面に何かを印刷する
- 世界IDを変更する
- 結果として返す
((),__)
。
今メインはひどく見えます。 askUser関数でも同じことをしましょう:
askUser :: World -> ([Integer],World)
に
askUser :: IO [Integer] askUser = do putStrLn " :" input <- getLine let maybeList = getListFromString input in case maybeList of Just l -> return l Nothing -> askUser
後
askUser w0 = let (_,w1) = putStrLn "Enter a list of numbers:" in let (input,w2) = getLine w1 in let (l,w3) = case getListFromString input of Just l -> (l,w2) Nothing -> askUser w2 in (l,w3)
一見、しかしbutい。 これらの不器用な
w*
変数を見てください。
私たちが学んだ教訓は、機能的に純粋な言語でのI / Oの素朴な実装はひどいように見えることです。
幸いなことに、この問題を解決するためのより直接的なアプローチがあります。 パターンが見えます。 各行は次のように表されます。
let (y,w') = action xw in
最初のパラメーター
x
不要な場合でも、結果はカップル
(answer, newWorldValue)
ます。 各関数
f
は、次のような型が必要です。
f :: World -> (a,World)
さらに、これらの関数の使用方法が非常に似ていることにも気付きました。
let (y,w1) = action1 w0 in let (z,w2) = action2 w1 in let (t,w3) = action3 w2 in ...
各アクションは、0〜n個のパラメーターを使用できます。 また、特に、各アクションは入力として前の行の結果を取ることができます。
たとえば、次のように書くことができます。
let (_,w1) = action1 x w0 in let (z,w2) = action2 w1 in let (_,w3) = action3 xz w2 in ...
そして、もちろん、
actionN w :: (World) -> (a,World)
。
重要! 注意が必要なパターンは2つだけです。
let (x,w1) = action1 w0 in let (y,w2) = action2 x w1 in
そして
let (_,w1) = action1 w0 in let (y,w2) = action2 w1 in
そして今、ちょっとしたトリックがあります。
世界の状態を保持する変数を「消滅」させます。 2つの文字列を
bind
ます。 これを行うために、
bind
関数を作成します。
彼女のタイプは最初は奇妙に見えます:
bind :: (World -> (a,World)) -> (a -> (World -> (b,World))) -> (World -> (b,World))
(World -> (a,World))
はIOアクションのタイプであることを忘れないでください。
簡単にするために名前を変更しましょう:
type IO a = World -> (a, World)
いくつかの例:
getLine :: IO String print :: Show a => a -> IO ()
getLine
は、パラメータとしてワールドを取り、ペア
(String,World)
を返すIOアクションです。
getLine
型は
IO String
なると言えます。
また、「IOで囲まれた」文字列を返すIOアクションとして認識することもできます。
print
機能も非常に興味深いです。 入力パラメーターを受け取り、表示します。 しかし、実際には2つのパラメーターが必要です。 最初のパラメーターは表示される値であり、2番目は世界の状態です。 結果として、ペア
((),World)
返します。 つまり、世界の状態を変更しますが、データを返しません。
この型は、
bind
関数の型定義を簡素化します。
bind :: IO a -> (a -> IO b) -> IO b
bind
は引数として2つのIOアクションを取り、別のIOアクションを返します。
次に、いくつかの重要なパターンを更新します。 最初はこのようなものでした:
let (x,w1) = action1 w0 in let (y,w2) = action2 x w1 in (y,w2)
タイプに注意してください。
action1 :: IO a action2 :: a -> IO b (y,w2) :: IO b
おなじみですね。
(bind action1 action2) w0 = let (x, w1) = action1 w0 (y, w2) = action2 x w1 in (y, w2)
基本的な考え方は、この関数を使用してWorldパラメーターを非表示にすることです。 行こう! 取得したいものの一部を次に示します。
let (line1,w1) = getLine w0 in let ((),w2) = print line1 in ((),w2)
そして今、バインド関数を使用します:
(res,w2) = (bind getLine (\l -> print l)) w0
printは
(World -> ((),World))
であるため、
res = ()
(null型)であることがわかります。
ここに特別なストリートマジックが表示されない場合は、3行のプログラムを作成してみてください。
let (line1,w1) = getLine w0 in let (line2,w2) = getLine w1 in let ((),w3) = print (line1 ++ line2) in ((),w3)
次のようなものです:
(res,w3) = bind getLine (\line1 -> bind getLine (\line2 -> print (line1 ++ line2)))
気づいた?
はい、これ以上World一時変数はありません!
これはMAです。 GI 私は
しかし、別の構文を使用できます。
bind
を
(>>=)
置き換えましょう。
(>>=)
これは中置関数であり、
(+)
; リコール
3 + 4 ⇔ (+) 3 4
(res,w3) = getLine >>= \line1 -> getLine >>= \line2 -> print (line1 ++ line2)
ほほほ! 明けましておめでとうございます! Haskellには構文シュガーがあります:
do x <- action1 y <- action2 z <- action3 ...
次のものに置き換えることができます。
action1 >>= \x -> action2 >>= \y -> action3 >>= \z -> ...
action2
で
x
を使用し、
action2
で
x
を
y
とともに使用できます。
しかし、
<-
使用しない文字列はどうでしょうか?
簡単!
blindBind
関数があります:
blindBind :: IO a -> IO b -> IO b blindBind action1 action2 w0 = bind action (\_ -> action2) w0
私はこの表現を意図的に単純化しませんでした。
もちろん、コードをよりシンプルにしたい場合は、演算子
(>>)
使用できます。
そしてそう
do action1 action2 action3
に変わる
action1 >> action2 >> action3
ちなみに、もう1つの非常に便利な機能を次に示します。
putInIO :: a -> IO a putInIO x = IO (\w -> (x,w))
これは、純粋な値を「IOコンテキスト」にプッシュする標準的な方法です。
通常、
putInIO
は
putInIO
と呼ばれます。
Haskellを学習するとき、この関数名は非常にわかりにくいものです。
return
他の言語のピア
return
大きく異なります。
03_地獄/ 01_IO / 21_Detailled_IO.lhs
最後に、例を書き換えてみましょう。
askUser :: IO [Integer] askUser = do putStrLn " , :" input <- getLine let maybeList = getListFromString input in case maybeList of Just l -> return l Nothing -> askUser main :: IO () main = do list <- askUser print $ sum list
次のように書き換えることができます。
import Data.Maybe maybeRead :: Read a => String -> Maybe a maybeRead s = case reads s of [(x,"")] -> Just x _ -> Nothing getListFromString :: String -> Maybe [Integer] getListFromString str = maybeRead $ "[" ++ str ++ "]" askUser :: IO [Integer] askUser = putStrLn " , :" >> getLine >>= \input -> let maybeList = getListFromString input in case maybeList of Just l -> return l Nothing -> askUser main :: IO () main = askUser >>= \list -> print $ sum list
これで、このコードをコンパイルして、機能することを確認できます。
そして、
(>>)
と
(>>=)
なしでこれがどのように見えるか想像してみましょう。
03_地獄/ 01_IO / 21_Detailled_IO.lhs
03_地獄/ 02_Monads / 10_Monads.lhs
モナド
次に、秘密を明らかにしましょう
IO
はモナドです。
モナドを使用すると、構文糖衣記法を使用できることを意味します。
しかし、最も重要なのはデザインパターンです。これにより、よりクリーンで理解しやすいコードを記述できます。
重要な注意 :
- モナドは必ずしも副作用に関連付けられているわけではありません!
多くの純粋なモナドがあります。- モナドの本質は計算の構成にあります
Haskell言語に関しては、
Monad
は型クラスです。
このクラスのインスタンスになるには、関数
(>>=)
および
return
を定義する必要があります。
関数
(>>)
は
(>>=)
基づいて自動的に作成されます。
Monad
クラスの(ほぼ完全な)定義を次に示します。
class Monad m where (>>=) :: ma -> (a -> mb) -> mb return :: a -> ma (>>) :: ma -> mb -> mb f >> g = f >>= \_ -> g -- -- fail :: String -> ma fail = error
備考:
class
キーワードはあなたが思うものではありません。
Haskell のクラスは、OOPのクラスではありません 。
Haskellのクラスは、JavaまたはC#のインターフェースに似ています。
それをtypeclass
と呼ぶ方が良いでしょう。
これは多くのクラスを意味します。
型がこのクラスに属するためには、その型はクラスのすべての機能を実装する必要があります。- この特定の場合、タイプ
m
は引数を取ることができるタイプm
なければなりません。
たとえば、IO a
、およびMaybe a
[a]
など。- 便利なモナドであるためには、関数が特定の法律に準拠している必要があります。
あなたの機能がこれらの法律に違反する場合、奇妙なことが起こります:
return a >>= k == ka m >>= return == m m >>= (\x -> kx >>= h) == (m >>= k) >>= h
たぶんモナド
Monad
インスタンスには多くのタイプがあります。
最も簡単な例は
Maybe
です。
Maybe
値のセットがある場合、モナドを使用してそれらを操作できます。 特に、ネストされた
if..then..else..
を取り除くと便利です
if..then..else..
複雑な銀行業務を想像してください。マイナスに入らずに取引の履歴がある場合にのみ、700ユーロのボーナスを請求できます。
deposit value account = account + value withdraw value account = account - value eligible :: (Num a,Ord a) => a -> Bool eligible account = let account1 = deposit 100 account in if (account1 < 0) then False else let account2 = withdraw 200 account1 in if (account2 < 0) then False else let account3 = deposit 100 account2 in if (account3 < 0) then False else let account4 = withdraw 300 account3 in if (account4 < 0) then False else let account5 = deposit 1000 account4 in if (account5 < 0) then False else True main = do print $ eligible 300 -- True print $ eligible 299 -- False
03_地獄/ 02_Monads / 10_Monads.lhs
03_地獄/ 02_モナド/ 11_Monads.lhs
そして、MaybeとそのMonadエンティティを使用して、このコードで物事を整理しましょう。
deposit :: (Num a) => a -> a -> Maybe a deposit value account = Just (account + value) withdraw :: (Num a,Ord a) => a -> a -> Maybe a withdraw value account = if (account < value) then Nothing else Just (account - value) eligible :: (Num a, Ord a) => a -> Maybe Bool eligible account = do account1 <- deposit 100 account account2 <- withdraw 200 account1 account3 <- deposit 100 account2 account4 <- withdraw 300 account3 account5 <- deposit 1000 account4 Just True main = do print $ eligible 300 -- Just True print $ eligible 299 -- Nothing
03_地獄/ 02_モナド/ 11_Monads.lhs
03_地獄/ 02_モナド/ 12_Monads.lhs
すでに悪くはありませんが、さらに改善することができます:
deposit :: (Num a) => a -> a -> Maybe a deposit value account = Just (account + value) withdraw :: (Num a,Ord a) => a -> a -> Maybe a withdraw value account = if (account < value) then Nothing else Just (account - value) eligible :: (Num a, Ord a) => a -> Maybe Bool eligible account = deposit 100 account >>= withdraw 200 >>= deposit 100 >>= withdraw 300 >>= deposit 1000 >> return True main = do print $ eligible 300 -- Just True print $ eligible 299 -- Nothing
それで、モナドがコードをよりエレガントにすることができることを証明しました。
一般的に、
Maybe
同様の使用は、ほとんどの命令型言語で機能します。
これはかなり自然なデザインです。
重要な注意:
結果がNothing
である最初の計算は、以降の計算をすべて停止します。
つまり、すべてのコードが実行されるわけではありません。
また、この最適化は、言語の遅延のおかげで、完全に無料で利用できます。
Maybe
定義
(>>=)
を使用して、このコードを書き換えることができます
Maybe
:
instance Monad Maybe where (>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b Nothing >>= _ = Nothing (Just x) >>= f = fx return x = Just x
Maybe
、このような小さな例でもモナドはその価値を証明した
Maybe
。
IO
モナドの使用も確認しました。 しかし、もっと興味深い例があります-リスト。
03_地獄/ 02_モナド/ 12_Monads.lhs
03_Hell / 02_Monads / 13_Monads.lhs
リストモナド
リストモナドを使用すると、非決定的な計算をモデル化できます。
例:
import Control.Monad (guard) allCases = [1..10] resolve :: [(Int,Int,Int)] resolve = do x <- allCases y <- allCases z <- allCases guard $ 4*x + 2*y < z return (x,y,z) main = do print resolve
MA GI。I .:
[(1,1,7),(1,1,8),(1,1,9),(1,1,10),(1,2,9),(1,2,10)]
リストモナド用の構文糖衣もあります:
print $ [ (x,y,z) | x <- allCases, y <- allCases, z <- allCases, 4*x + 2*y < z ]
モナドの完全なリストは提供しませんが、それらはたくさんあります。
モナドを使用すると、多くのタスクを簡素化できます。
特に、モナドは次の場合に非常に便利です。
- IO
- 非決定的コンピューティング、
- 擬似乱数の生成、
- 構成ストレージ
- 状態で動作します
- ...
この場所に着いたら、おめでとうございます!
これで
03_Hell / 02_Monads / 13_Monads.lhs
アプリ
このセクションはHaskellの研究には直接適用されません。一部の詳細にのみ注意を払っています。
04_付録/ 01_More_on_infinite_trees / 10_Infinite_Trees.lhs
無限の木についてもう一つ
Infinite Structuresセクションでは、いくつかの単純な無限構造を見てきました。残念ながら、ツリーには2つのプロパティがありません。
- ツリーノードに重複はありません
- 整然とした木
このセクションでは、最初のプロパティを扱います。
2番目については、少し弱めますが、できるだけ理想に近づけるようにします。
まず、一連の疑似乱数からリストを作成しましょう。
shuffle = map (\x -> (x*3123) `mod` 4331) [1..]
メモリを更新するには、実装を複製します
treeFromList
treeFromList :: (Ord a) => [a] -> BinTree a treeFromList [] = Empty treeFromList (x:xs) = Node x (treeFromList (filter (<x) xs)) (treeFromList (filter (>x) xs))
および
treeTakeDepth
:
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 = do putStrLn "take 10 shuffle" print $ take 10 shuffle putStrLn "\ntreeTakeDepth 4 (treeFromList shuffle)" print $ treeTakeDepth 4 (treeFromList shuffle)
% runghc 02_Hard_Part/41_Infinites_Structures.lhs take 10 shuffle [3123,1915,707,3830,2622,1414,206,3329,2121,913] treeTakeDepth 4 (treeFromList shuffle) < 3123 : |--1915 : | |--707 : | | |--206 : | | `--1414 : | `--2622 : | |--2121 : | `--2828 : `--3830 : |--3329 : | |--3240 : | `--3535 : `--4036 : |--3947 : `--4242
やった!稼いだ!ただし、ブランチに追加するものがある場合にのみ機能します。
例:
treeTakeDepth 4 (treeFromList [1..])
無限に実行されます。
これは、コードが式の先頭を取得しようとしているため
filter (<1) [2..]
です。
しかし
filter
、式の結果が空のリストであることを理解するほど賢くはありません。
ただし、これは非厳格なプログラムができることの良い例です。
読者のための練習:
- 数があることを証明無限ループに陥ったが。
n
treeTakeDepth n (treeFromList shuffle)
- の上限を見つけます
n
。 - そのような
shuffle
リストがないことを証明し、どちらを実行することにより、プログラムは終了します。
04_付録/ 01_More_on_infinite_trees / 10_Infinite_Trees.lhs
04_付録/ 01_More_on_infinite_trees / 11_Infinite_Trees.lhs
Davateはわずかに変更されて
treeFromList
おり
shuffle
、この問題を取り除くために作成されています。
最初の問題は私たちの実装における乱数の不足です
shuffle
。異なる数値
のみを生成しました
4331
。
機能を改善します
shuffle
。
shuffle = map rand [1..] where rand x = ((px) `mod` (x+c)) - ((x+c) `div` 2) px = m*x^2 + n*x + o -- some polynome m = 3123 n = 31 o = 7641 c = 1237
このバージョンの関数は、値に上限と下限がないので(私は心から願っています)優れています。しかし、シャッフルの改善は、無限ループを回避するのに十分ではありません。
厳密に言えば、リストが空かどうかはわかりません
filter (<x) xs
。
この問題を解決するために、バイナリツリーの実装を少し壊します。新しい実装では、一部のノードで次の条件が満たされません。
左の要素(または右)は、ツリーのルートの値よりも厳密に小さい(または大きい)必要があります。
この場合、ツリーは実質的に順序付けられたままになります。さらに、ツリーを作成する段階で、ノードの一意性を確保します。
新しいバージョンで
treeFromList
は、単にに置き換えまし
filter
た
safefilter
。
treeFromList :: (Ord a, Show a) => [a] -> BinTree a treeFromList [] = Empty treeFromList (x:xs) = Node x left right where left = treeFromList $ safefilter (<x) xs right = treeFromList $ safefilter (>x) xs
この関数は
safefilter
ほぼ同じです
filter
が、無限ツリーを処理するときに無限ループに陥ることはありません。10,000ステップで適切なアイテムが見つからない場合、検索を中止します。
safefilter :: (a -> Bool) -> [a] -> [a] safefilter fl = safefilter' fl nbTry where nbTry = 10000 safefilter' _ _ 0 = [] safefilter' _ [] _ = [] safefilter' f (x:xs) n = if fx then x : safefilter' f xs nbTry else safefilter' f xs (n-1)
プログラムを実行して喜ぶ:
main = do putStrLn "take 10 shuffle" print $ take 10 shuffle putStrLn "\ntreeTakeDepth 8 (treeFromList shuffle)" print $ treeTakeDepth 8 (treeFromList $ shuffle)
異なる値の表示間の遅延が同じではないことに気づいたかもしれません。
これは、Haskellが必要に応じて各値を計算するためです。
この場合、番号が画面に表示されるときに必要になります。
検索の深さをから
8
に増やしても
100
、この
関数は機能しますが、同時にすべてのRAMを消費することはありません!
読者のための練習:
deep
andの値が大きい場合でもnbTry
、関数は正常に機能しますが、最悪の場合、指数関数的な成長が予想されます。
の可能な最悪のリストオプションを見つけますtreeFromList
。
ヒント:([0,-1,-1,....,-1,1,-1,...,-1,1,...]
)について考えます。- 最初は
safefilter
次のように実装しようとしました:
safefilter' fl = if filter f (take 10000 l) == [] then [] else filter fl
, .
- ,
shuffle
.
, , 100% .
(,safefilter'
)
f
treeFromList' shuffle. .
treeFromList' [] n = Empty treeFromList' (x:xs) n = Node x left right where left = treeFromList' (safefilter' (<x) xs (fn) right = treeFromList' (safefilter' (>x) xs (fn) f = ???
04_Appendice/01_More_on_infinite_trees/ 11_Infinite_Trees.lhs
( , )
ありがとう
/r/haskell
と
/r/programming
。
あなたのコメントは非常に貴重です。
特に、英語のテキストの更新に費やした時間について、Emmに 1000回感謝します。ありがとうございます