1

それで、私は Paul Hudak の本「The Haskell School of Expression」を読んでいて、そこでの演習に行き詰まっています。

ここに行きます

関数 fix が次のように定義されているとします。 

fix f = f (fix f)

の主なタイプはfix何ですか? それは私が知っている、それですb -> b -> b

しかし、私は方法fixが定義されていることを理解していません。それは無限再帰に入りませんか?

また、関数を次のremainderように定義します。 

remainder :: Integer -> Integer -> Integer
remainder a b = if a < b then a 
                else remainder (a - b) b

非再帰的であるようにremainderusing を書き換えます。fix

4

2 に答える 2

3

まず第一に、修正の主なタイプは実際には( のみが と同じである(b -> b) -> bことを思い出してください) です。b -> (b -> b)b -> b -> b

厳密な言語では、このような定義は無限再帰になりますが、Haskell は遅延であるため、関数への引数は、必要な時点でのみ評価されます。たとえば、 を定義できますfactorial。

-- with recursion
factorial :: Int -> Int
factorial n = if n == 0 then 1 else n * factorial (n-1)

-- with `fix`
factorial' :: Int -> Int
factorial' = fix (\f n -> if n == 0 then 1 else n * f (n - 1))

同じパターンに従って、 を定義できるはずですremainder。

于 2016-11-19T17:04:34.047 に答える
2

少し遊んでみると

fix f         = f (fix f)                                            -- definition
fix f     a   = f (fix f) a                                          -- eta expansion
fix f     a b = f (fix f) a b                                        -- eta expansion
remainder a b = if a < b then a else remainder (a - b) b             -- definition
-- we want  remainder = fix f:                                       -- equation
fix f     a b = if a < b then a else (fix f)   (a - b) b             -- substitution
       = (\g -> if a < b then a else g         (a - b) b) (fix f)    -- abstraction
   = fix (\g -> \a b -> if a < b then a else g (a - b) b) a b        -- abstraction

したがって

remainder = 
     fix (\g     a b -> if a < b then a else g (a - b) b)            -- eta reduction
于 2016-11-19T19:28:09.907 に答える