13

だから私はHaskellを独学しようとしています。私は現在、Learn You a Haskell for Great Goodの第 11 章にいて、99 Haskell ProblemsとProject Euler Problemsに取り組んでいます。

物事は順調に進んでいますが、「変数」を追跡する必要があるときはいつでも、常に何かをしていることに気付きます。これらの「変数」をパラメーターとして受け入れ、状況に応じて異なる値を再帰的に供給する別の関数を作成するだけです。例を挙げて説明すると、Project Euler の問題 7 に対する私の解決策は、10001 番目の素数を見つけることです。

answer :: Integer
answer = nthPrime 10001

nthPrime :: Integer -> Integer
nthPrime n
  | n < 1 = -1
  | otherwise = nthPrime' n 1 2 []


nthPrime' :: Integer -> Integer -> Integer -> [Integer] -> Integer
nthPrime' n currentIndex possiblePrime previousPrimes
  | isFactorOfAnyInThisList possiblePrime previousPrimes = nthPrime' n currentIndex theNextPossiblePrime previousPrimes
  | otherwise = 
    if currentIndex == n 
      then possiblePrime 
      else nthPrime' n currentIndexPlusOne theNextPossiblePrime previousPrimesPlusCurrentPrime
        where currentIndexPlusOne = currentIndex + 1
              theNextPossiblePrime = nextPossiblePrime possiblePrime
              previousPrimesPlusCurrentPrime = possiblePrime : previousPrimes

私はあなたがアイデアを得ると思います。このソリューションをより効率的にすることができるという事実も無視しましょう。私はこれを認識しています。

ですから、私の質問は 2 部構成の質問です。まず、私は Haskell について間違っているのでしょうか? 私は命令型プログラミングの考え方にとらわれていて、Haskell を適切に受け入れていないのでしょうか? もしそうなら、私が感じているように、どうすればこれを避けることができますか? 私が Haskell のように考えるのに役立つかもしれない、あなたが私に指摘できる本や情報源はありますか?

あなたの助けは大歓迎です、

-アサフ

4

6 に答える 6

14

私は命令型プログラミングの考え方に固執していて、Haskellを適切に受け入れていませんか？

あなたは立ち往生していません、少なくとも私はそうは思わない。あなたが経験することは絶対に正常です。命令型言語で作業しているときに、プログラミングの問題を非常に具体的な観点から、つまりvan Neumannマシンの観点から見ることを（おそらく知らずに）学びました。

たとえば、いくつかの数のシーケンスを含むリストを作成するという問題がある場合（たとえば、最初の1000個の偶数が必要な場合）、すぐに次のことを考えます。リンクリストの実装（おそらくプログラミング言語の標準ライブラリから） 、ループと、開始値に設定した変数をしばらくループし、2を追加して変数を更新し、リストの最後に配置します。

マシンにサービスを提供することを主にどのように考えているかわかりますか？メモリの場所、ループなど！命令型プログラミングでは、特定のメモリセルを特定の順序で操作して、常にソリューションに到達する方法について考えます。（これが、初心者が（命令型）プログラミングの学習を困難に感じる理由の1つです。プログラマー以外の人は、問題を一連のメモリ操作に減らすことで問題を解決することに慣れていません。なぜそうすべきなのですか？しかし、それを学んだら、命令型の世界では、力を持っています。機能的なプログラミングでは、それを学ぶ必要があります。）

関数型プログラミング、特にHaskellでは、リストの構築法則を述べるだけです。リストは再帰的なデータ構造であるため、この法則ももちろん再帰的です。私たちの場合、たとえば次のように言うことができます。

constructStartingWith n = n : constructStartingWith (n+2)

そして、ほぼ完了です！最終的なリストにたどり着くには、どこから始めて、いくつ欲しいかを言うだけです。

result = take 1000 (constructStartingWith 0)

より一般的なバージョンのconstructStartingWithがライブラリで利用可能であることに注意してください。これは呼び出されiterate、開始値だけでなく、現在のリスト要素から次のリスト要素を作成する関数も受け取ります。

iterate f n = n : iterate f (f n)
constructStartingWith = iterate (2+)   -- defined in terms of iterate

別のアプローチは、リストを簡単に作成できる別のリストがあると想定することです。たとえば、最初のn個の整数のリストがある場合、各要素に2を掛けることで、偶数の整数のリストに簡単に入れることができます。これで、Haskellの最初の1000（非負）整数のリストは単純になります。

[0..999]

そしてmap、各引数に与えられた関数を適用することによってリストを変換する関数があります。必要な関数は、要素を2倍にすることです。

double n = 2*n

したがって：

result = map double [0..999]

後で、より多くのショートカットを学習します。たとえば、を定義する必要はありませんがdouble、セクションを使用できます。(2*)または、リストをシーケンスとして直接書き込むこともできます。[0,2..1998]

しかし、これらのトリックをまだ知らなくても、気分が悪くなることはありません！あなたが今直面している主な課題は、最初の1000個の偶数のリストを作成する問題が2段階の問題であることがわかる精神を発達させることです：a）すべての偶数のリストがどのように見えるかを定義しますb）取るそのリストの特定の部分。との手書きバージョンをまだ使用している場合でも、そのように考え始めると完了です。iteratetake

オイラー問題に戻る：ここでは、トップダウン方式を使用できます（そして、実際に知っておくべきいくつかの基本的なリスト操作関数：、、、head）。まず、素数のリストがすでにある場合は、最初の1000を削除し、残りの頭を取得して1001番目の素数を取得できます。dropfilterany

result = head (drop 1000 primes)

無限のリストから任意の数の要素を削除した後でも、そこから選択する空でないリストが残っていることがわかっているheadため、ここでの使用headは正当化されます。1000を超える素数があるかどうかわからない場合は、次のように記述してください。

result = case drop 1000 primes of
    [] -> error "The ancient greeks were wrong! There are less than 1001 primes!"
    (r:_) -> r

さて、難しい部分です。続行する方法がわからないので、いくつかの擬似コードを書くことができます。

primes = 2 : {-an infinite list of numbers that are prime-}

2が最初の素数、いわばベースケースであることは確かです。したがって、それを書き留めることができます。埋められていない部分は、私たちに考えるべきことを与えてくれます。たとえば、リストは明らかな理由で2より大きい値で開始する必要があります。したがって、洗練された：

primes = 2 : {- something like [3..] but only the ones that are prime -}

さて、これは人が認識することを学ぶ必要があるパターンが現れるポイントです。これは確かに述語filter、すなわち素数によって編集されたリストです（素数をチェックする方法がまだわからなくても、論理構造が重要なポイントです（そして、私たちは確かに素数のテストが可能です！））。これにより、より多くのコードを記述できます。

primes = 2 : filter isPrime [3..]

見る？ほぼ完了です。3つのステップで、かなり複雑な問題を減らし、残りの記述は非常に単純な述語だけになります。繰り返しますが、擬似コードで書くことができます：

isPrime n = {- false if any number in 2..n-1 divides n, otherwise true -}

そしてそれを洗練することができます。これはすでにほとんどhaskellなので、簡単すぎます。

isPrime n = not (any (divides n) [2..n-1])
divides n p = n `rem` p == 0

まだ最適化を行っていないことに注意してください。たとえば、偶数が素数ではないことがわかっているので、奇数だけを含むようにすぐにフィルタリングされるリストを作成できます。さらに重要なのは、isPrimeで試す必要のある候補者の数を減らしたいということです。そして、ここでは、いくつかの数学的知識が必要です（もちろん、これをC ++またはJavaでプログラムした場合も同様です）。これは、nテストしているものが素数で割り切れるかどうかを確認するだけで十分であり、二乗が。より大きい素数による除算性をチェックする必要はありませんn。幸いなことに、私たちはすでに素数のリストを定義しており、そこから候補のセットを選ぶことができます！私はこれを運動として残します。

標準ライブラリと、セクションやリスト内包表記などの構文糖衣構文の使用方法を後で学び、徐々に独自の基本関数を書くことを諦めます。

後で、命令型プログラミング言語で何かをやり直さなければならないとき、無限のリスト、高階関数、不変データなどなしでは生きていけないことに気付くでしょう。これは、Cからアセンブラーに戻るのと同じくらい難しいでしょう。

楽しむ！

于 2011-12-09T11:44:35.570 に答える
12

最初は必須の考え方を持っていても大丈夫です。時間が経つにつれて、あなたは物事にもっと慣れ、あなたがより機能的なプログラムを持つことができる場所を見始めるでしょう。練習は完璧を作る。

可変変数の操作に関しては、変数を関数パラメーターに変換し、反復を末尾再帰に変換するという経験則に従うと、今のところそれらを保持できます。

于 2011-12-09T02:08:45.310 に答える
4

頭のてっぺんから：

于 2011-12-09T02:03:10.003 に答える
3

あなたのコードから Haskell のようなコードへの大きな変化は、高次関数、パターン マッチング、および遅延をより適切に使用していると思います。たとえば、次のようにnthPrime関数を記述できます (同様のアルゴリズムを使用して、効率を無視します)。

nthPrime n = primes !! (n - 1) where
  primes = filter isPrime [2..]
  isPrime p = isPrime' p [2..p - 1]
  isPrime' p [] = True
  isPrime' p (x:xs) 
    | (p `mod` x == 0) = False
    | otherwise = isPrime' p xs

例: nthPrime 47 を返します。

  • このisPrime'関数は、if ステートメントに依存するのではなく、パターン マッチングを使用して関数を実装します。
  • 値はprimesすべての素数の無限リストです。haskell は怠惰なので、これはまったく問題ありません。
  • filter再帰を使用してその動作を再実装するのではなく、使用されます。

より多くの経験を積めば、より慣用的な Haskell コードを書けるようになるでしょう - それは経験によって自動的に起こります。ですから、心配する必要はありません。ただ練習を続け、他の人のコードを読んでください。

于 2011-12-09T06:14:57.653 に答える
2

多様性のためだけに、別のアプローチ！怠惰の強い使い方...

module Main where

nonmults :: Int -> Int -> [Int] -> [Int]
nonmults n next [] = []
nonmults n next l@(x:xs)
   | x < next = x : nonmults n next xs
   | x == next = nonmults n (next + n) xs
   | otherwise = nonmults n (next + n) l

select_primes :: [Int] -> [Int]
select_primes [] = []
select_primes (x:xs) = 
  x : (select_primes $ nonmults x (x + x) xs)

main :: IO ()
main = do
  let primes = select_primes [2 ..]
  putStrLn $ show $ primes !! 10000 -- the first prime is index 0 ...
于 2011-12-10T05:26:39.890 に答える
1

関数型プログラミングや数学を使用せずにあなたの質問に答えようと思います。あなたがそれを理解するとは思わないからではなく、あなたの質問は非常に一般的であり、私が説明しようとする考え方から他の人が恩恵を受けるかもしれないからです。私は Haskell の専門家ではありませんが、次のことを実現することで、あなたが説明したメンタルブロックを乗り越えました。

1. Haskell はシンプル

Haskell や、私がよく知らないその他の関数型言語は、C、Java、Python などの「通常の」言語とは明らかに大きく異なります。 A) 彼らはそれを理解していない、そして B) それは彼らがすでに知っていることよりも複雑である. Haskell を非常に客観的に見ると、次の 2 つの予想が完全に間違っていることがわかります。

「しかし、私はそれを理解していません:(」

実際にそうです。Haskell やその他の関数型言語のすべては、ロジックとパターンの観点から定義されています。「すべての Meep が Moop であり、すべての Moop が Moor である場合、すべての Meep は Moors ですか?」というような単純な質問に答えることができれば、おそらく Haskell Prelude を自分で書くことができます。この点をさらに裏付けるために、Haskell リストは Haskell 用語で定義されており、特別なブードゥー教の魔法ではないことを考慮してください。

「でも複雑です」

それは実際には反対です。そのシンプルさはむき出しであり、私たちの脳は最初はそれをどうするかを理解するのに苦労します. 他の言語と比較して、Haskell は実際には「機能」がかなり少なく、構文もはるかに少ないです。Haskell コードを読んでみると、ほとんどすべての関数定義がスタイル的に同じに見えることに気付くでしょう。これは、たとえばクラス、インターフェイス、for ループ、try/catch ブロック、無名関数などの構造を持つ Java とは大きく異なります。それぞれに独自の構文とイディオムがあります。

あなたは言及$し.ましたが、繰り返しになりますが、これらは他のHaskell関数と同じように定義されており、必ずしも使用する必要はありません. ただし、これらを利用できなかった場合、時間の経過とともに、これらの関数がいかに便利であるかに気付いたときに、これらの関数を自分で実装する可能性があります。

2. Haskell バージョンはありません

Haskell では、物事を好きなように正確に定義する自由があるため、これは実際には素晴らしいことです。他のほとんどの言語は、人々がプログラムにつなぎ合わせる構成要素を提供します。Haskell では、ビルディング ブロックを使用してビルドする前に、まずビルディング ブロックとは何かを定義する必要があります。

多くの初心者は、「Haskell で For ループを実行するにはどうすればよいですか?」などの質問をします。助けようとしている罪のない人々は、おそらくヘルパー関数、追加の Int パラメーター、および 0 になるまでの末尾の再帰を含む、不幸な答えを返すでしょう。確かに、この構文は for ループのようなものを計算できますが、それはforループですか、それはforループの代わりではありません、そして決して似ていません実行の流れを考えると for ループに。状態をシミュレートする State モナドも同様です。静的変数が他の言語で行うのと同様のことを達成するために使用できますが、決して同じことではありません。ほとんどの人は、この種の質問に答えるときに、同じではないという最後の一口を省きます。それは、自分でそれに気付くまで、人々をさらに混乱させるだけだと思います.

3. Haskell はロジック エンジンであり、プログラミング言語ではない

これはおそらく、私が言おうとしている最も真実でない点ですが、聞いてください。命令型プログラミング言語では、マシンに何かを実行させたり、アクションを実行させたり、状態を変更させたりすることに関心があります。Haskell では、物事とは何か、それらがどのように振る舞うべきかを定義しようとします。私たちは通常、特定の時間に何かが行われていることに関心はありません。これには確かにメリットとデメリットがありますが、それはまさにその通りです。これは、「プログラミング言語」と言うときにほとんどの人が考えるものとは大きく異なります。

以上が、命令的な考え方から抜け出し、より機能的な考え方に移行する方法です。Haskell がどれほど賢明であるかを理解することで、自分のコードをおかしなものに思わなくなります。これらの方法で Haskell について考えることが、より生産的な Haskell になるのに役立つことを願っています。

于 2013-12-16T00:53:11.427 に答える