3

再帰関数をポイントフリー定義に変換できるかどうか知りたいです。

簡単な再帰関数を取ると。

factorial :: int-> int
factorial 0=1
factorial n+1= (n+1) *factorial n

非再帰的な定義がある場合。

factorial :: int-> int
factorial n= product [1..n]  
   <=> factorial n = product.enumFromTo 1 n 
   <=> factorial   = product.enumFromTo 1  

しかし、再帰定義で同じことを行うにはどうすればよいですか?

私が質問している理由は、transformationsApply無意味にしたいからです。

transformationsApply :: Eq a => a -> ([a] -> [a]) -> [([a], [a])] -> [a] -> Maybe [a]
transformationsApply _ _ [] _= Nothing
transformationsApply wc func ((a,b):xs) (y:ys)
   = orElse (transformationApply wc func (y:ys) (a,b)) 
            (transformationsApply wc func xs (y:ys))

transformationApply上記で使用されるは、次のように定義されます

transformationApply :: Eq a => a -> (([a] -> [a]) -> ([a] -> (([a], [a]) -> Maybe [a])))

transformationApply wc func xs (a,b) 
   = mmap ((substitute wc b).func) (match wc a xs)
4

4 に答える 4

5

コードを理解できない無意味な形式に変換するよりも、コードを読みやすくすることをお勧めします。

関数をポイントフリー形式に変換する最も簡単な方法は、ラムダボットに尋ねることです。再帰関数がある場合、fix を使用してそれを非再帰関数に変換できます。これが関数の例ですfact(ラムダボットが提供したものからの直接変換)、それがどれほど読みやすいかを見ることができます。

import Control.Monad
import Data.Function


if' :: Bool -> a -> a -> a
if' True  x _ = x
if' False _ y = y

fact = fix $ ap (flip if' 1 . (0 ==)) . ap (*) . (. subtract 1)
于 2013-11-10T10:07:37.023 に答える
1

ほとんどの再帰関数を自動的にポイント フリー フォームに変換できますが、他の人が示しているように、結果は見苦しく、役に立たないものになる可能性があります。

ただし、ここにあるのは実際には一般的な再帰ではありません。リストに折り畳みがあり、各リスト要素に関数を適用してからそれらを組み合わせた結果を構築します。

Haskell には、折り畳みやその他の方法で特にリストを再帰するための構成要素があり、これにより、はるかにきれいな結果が得られます。(ただし、それが改善であるかどうかについては、あなたの判断が必要です。) 最も一般的なそのようなビルディング ブロックは、関数foldrmapです。実際、あなたの例は次のように書き直すことができます:

transformationsApply :: Eq a => a -> ([a] -> [a]) -> [([a], [a])] -> [a] -> Maybe [a]
transformationsApply wc func xs (y:ys) =
    foldr orElse Nothing (map (transformationApply wc func (y:ys)) xs)
transformationsApply _ _ [] [] = Nothing

(最後の行は、まれなケースのためです: 元の関数は、 xs リストが空である場合を除いて、すべての場合に最後の引数が空であるかどうかをチェックします。これは必要ないかもしれません。)

于 2013-11-11T07:04:01.610 に答える
1

から始めてfactorial、まず型ケース弁別子が必要です。これは、数字のパターン マッチングをカプセル化するためです。

num :: (Num a) => b -> (a -> b) -> a -> b
num z _  0 = z
num _ nz x = nz x

今、アイデンティティを使って(g =<< f) x = g (f x) x、私たちは書きます

import Control.Applicative
import Data.Function (fix)

fact :: (Num c, Enum c) => c -> c
fact = num 1 ((*) =<< (fact.pred))

真に無意味な形式を得るにはfact、右にプッシュする必要がありfixます。

     = num 1 . ((*) =<<) . (.pred) $ fact
     = fix (num 1 . ((*) =<<) . (.pred))

Ørjan Johansen が指摘しているように、2 番目の関数に進みます(使用する明示的なパターンによって決定される、引数の強制順序の複雑さを無視する場合)。

transformationsApply :: Eq a => a -> ([a] -> [a]) -> [([a], [a])] -> [a] -> Maybe [a]
transformationsApply a b c d
   = foldr (orElse . transformationApply a b d) Nothing c

これはすでに非常に組み合わせ的に見えます。したがって、ここでは再帰foldrは によって明示的に表現されるのではなく、によってカプセル化されていfixます。

引数の順序をもう少し調整することもできますが、それはあまり面白くありません。

   = flip (foldr . (orElse .) . transformationApply a b) Nothing d c
   = flip (flip (foldr . (orElse .) . transformationApply a b) Nothing) c d
   = ...
于 2013-11-11T07:09:34.267 に答える