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

但是我怎样才能对递归定义做同样的事情呢？

我问的原因是我想让transformationsApplypointfree。

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

我建议让您的代码更具可读性，而不是尝试将其转换为难以理解的无点形式。

将函数转换为无点形式的最简单方法是询问 lambdabot。现在，当您拥有递归函数时，您可以使用 fix 将其转换为非递归函数。这是fact函数的示例（从 lambdabot 给出的直接转换），您可以看到它的可读性。

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 具有专门用于折叠和以其他方式在列表上递归的构建块，这将产生更漂亮的结果。（尽管您仍然需要使用自己的判断来判断它是否是一种改进。）最常见的此类构建块是函数foldr和map. 实际上，您的示例可以重写为：

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指出的那样，它本质上是一个正确的折叠（如果我们忽略参数强制顺序的复杂性，由你使用的显式模式决定）：

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 回答
0

我们需要一个内联分支操作，而

if' True  t _ = t
if' False _ e = e

流行另一种形式更有用。我会打电话的p

p check a | check a   = Right a
          | otherwise = Left  a

这足以定义if'

if' b t e = either (const e) (const t) . p (const b)

但有更好的属性

(\a -> if' (check a) (t a) (e a)) == either e t . p check

它让我们摆脱了第一个分支factorial

factorial' = either (const 1) (\n -> n * factorial (n-1)) . p (==0)

这意味着我们只需要以某种方式消除该(\n -> n * factorial (n-1))位。使用来自的(&&&)“扇出”组合器Control.Arrow

(&&&) :: (a -> b) -> (a -> c) -> (a -> (b, c))

我们有

(\n -> n * factorial (n-1)) == uncurry (*) . (id &&& factorial . (+ negate 1))

(-)由于切片模棱两可，这有点烦人。我将暂时离开它，但我们的最终功能是

factorial'' :: Int -> Int
factorial'' = 
  either (const 1) 
         (uncurry (*) 
          . (id &&& factorial'' . (+ negate 1))) 
  . p (==0)

并且定义的递归部分工作得很好。从技术上讲，该类型比那更通用

factorial'' :: (Eq a, Num a) => a -> a

这可能有点不令人满意，因为我们Eq现在需要约束，而模式匹配版本不需要。如果我们的数字有自然的析构函数可供我们使用，我们可以做得更好。例如，如果我们用“自然”构造函数和析构函数定义我们自己的自然值

data Nat = Z | S Nat

cons :: Maybe Nat -> Nat
cons Nothing  = Z
cons (Just n) = S n

uncons :: Nat -> Maybe Nat
uncons Z     = Nothing
uncons (S n) = Just n

我们可以在没有进一步的模式匹配的情况下完成所有其余的工作。让我们得到一个plus和一个mult

--  Z   + n = n
--  S m + n = S (m + n)    
plus n = maybe n (S . plus n) . uncons

--  Z   * n = Z
--  S m * n = n + (m * n)
mult n = maybe Z (plus n . mult n) . uncons

有了这些，我们有

naturalFact :: Nat -> Nat
naturalFact = maybe (S Z) (uncurry mult . (S &&& naturalFact)) . uncons

这是非常令人满意的。在不消除递归步骤并完全进入无点编程的 Squiggol 风格或完全对我们的所有模式匹配进行 Church 编码的情况下，这可能会尽可能令人满意。

于 2013-11-10T17:09:34.290 回答