6

haskellでハイパー演算関数を書こうとしています。

通常は次のように書かれてackermann(a,b,n)いますが、部分適用の目的では、最初に置く方が理にかなっていると思いますn。そういうものとして私はそれを呼んでいますhypOp n a b

replicate私が最も自然な使用法を見つけたフォームは、次のようなリストを折りたたむ。

Prelude> replicate 3 5
[5,5,5]
Prelude> foldr1 (*) $ replicate 3 5
125

フォールドに対する関数の引数に応じて、これは加算、乗算、べき乗、テトレーションなどになります。

非公式の概要：

hypOp 0 a _ = succ a
hypOp 1 a b = a + b = foldr1 (succ a) (replicate b a) --OFF BY ONE ISSUES, TYPE ISSUES
hypOp 2 a b = a * b = foldr1 (+) $ replicate b a
hypOp 3 a b = a ^ b = foldr1 (*) $ replicate b a
hypOp 4 a b = = foldr1 (^)

連想的な理由から、私は右の折り目を使用する必要があるという印象を受けています。これは、左の折り目（foldl'）で利用できる厳密さが役立つため、残念です。

右と左の折り目の問題

Prelude> foldl1 (^) $ replicate 4 2 --((2^2)^2)^2 = (4^2)^2 = 16^2 = 256 != 2 tetra 4
256
Prelude> foldr1 (^) $ replicate 4 2 --(2^(2^(2^2))) = 2^16 = 65536 == 2 tetra 4
65536

後継関数で最初から「開始」すると、1つずつ問題が発生します。代わりに、ベースフォールドの関数として（+）を使用しています

Prelude> let add a b = foldr1 (\a b -> succ b) $ replicate b a
Prelude> add 5 4
8
Prelude> add 10 5  --always comes out short by one, so i cant build off this
14

最初のいくつかnの値は、「手動で」実行されます。

Prelude> let mul a b = foldr1 (+) $ replicate b a
Prelude> let exp a b = foldr1 mul $ replicate b a
Prelude> let tetra a b = foldr1 exp $ replicate b a
Prelude> let pent a b = foldr1 tetra $ replicate b a
Prelude> let sixate a b = foldr1 pent $ replicate b a
Prelude> mul 2 3 --2+2+2
6
Prelude> exp 2 3 --2*2*2
8
Prelude> tetra 2 3 --2^(2^2)
16
Prelude> pent 2 3 --2 tetra (2 tetra 2) 
65536
Prelude> sixate 2 3
*** Exception: stack overflow

上記のアプローチによる正式な定義の私の試み：

hypOp :: Int -> Int -> Int -> Int
hypOp 0 a b = succ a
hypOp 1 a b  =  (+) a b  --necessary only bc off-by-one error described above
hypOp n a b = foldr1 (hypOp $ n-1) (replicate b a)

再帰配列を使用したその他の試み（重要な点で違いはありません）：

let arr = array (0,5) ( (0, (+)) : [(i, (\a b -> foldr1 (arr!(i-1)) (replicate b a)) ) | i <- [1..5]])
-- (arr!0) a b makes a + b
-- (arr!1) a b makes a * b, etc.

だから私の質問は...

  1. 一般的な提案、機能に対するさまざまなアプローチはありますか？haskellを使用して慣用的なスタイルでコーディングしようとするときに私の意図ではない非常に「命令型」のスタイルを使用することを除いて、オーバーフローを回避する方法を見つけることができないようです。
  2. 私のオフバイワンの問題にどのように対処できるので、一番下から「適切に」始めることができます。succ
  3. 厳格さと左対右の折り目。で働く方法はありseqますか？foldl1'上記の問題の代わりに使用しfoldr1て、上記の問題を回避する方法はありますか？
4

1 に答える 1

3

  1. ポイント3を参照してください。これらの操作をこのように定義することは機能し、オーバーフローなしで実行できますが、これは非常に非効率的なアプローチです。繰り返し加算を行うことになるため、実行時間は答えにおいて線形です。

  2. オフバイワンを取得している理由は、基本的に、IDfoldr1 fではなく使用しているためです。foldr f

    foldr (+) 0 [a, a, a] = a + (a + (a + 0)))
foldr1 (+) [a, a, a]  = a + (a + a)

    +の場合、アプリケーションが1つ少ないことに注意してくださいfoldr1。

  3. 引数の順序を単純に変更するのはどう(^)ですか？そうすれば、左の折り目を使用できます。

    Prelude Data.List> foldl1 (flip (^)) $ replicate 4 2
65536

    これで、厳密なバージョンを使用できますfoldl1'。オーバーフローすることはなくなりましたが、もちろん非常に非効率的です。

于 2011-05-11T16:17:41.263 に答える