Haskell +"删除参数"

Question

我有一个理论问题,一个朋友和我一直试图看,我们怎么做.我们有一个名为的函数palindrome,告诉我们String是否是回文.以下是我们实现它的方式(可能有更好的方法,但这就是我们更喜欢它的方式.)

palindrome :: String -> Bool
palindrome = \x -> (== reverse x) x

我们想要做的是remove我们在这里使用的Lambda,只使用部分应用程序和高阶函数.我们有几个关于如何做到这一点的想法,但它们都没有与我们制作的函数类型相匹配:

palindrome :: String -> Bool

最接近的方法之一是使用合成,但它返回一个函数,它接受两个字符串而不是一个,因为一个用于反向而另一个用于(==):

palindrome = (==) . reverse

也许,我们忘了什么或者我们没有看到什么.为了在不使用Lambda的情况下使用这两个函数,你会怎么做？

Answer 1

您可以使用<*>运算符作为(->)实例Applicative.

palindrome = (==) <*> reverse

<*>在某些上下文中,运算符有点像函数应用程序.在这种情况下,该上下文是" String作为一个参数的函数".所以你得到一个函数,它接受String并将它传递给两个函数,这两个函数也接受Strings,然后将前者的结果应用于后者.换句话说,f <*> g = \x -> f x (g x).

Answer 2

你现在有三个答案,但也许不是那么理解.

该问题是,你有两个X在右手边的,它看起来并不像有删除一个好办法.您需要一个具有以下签名之一的函数来"复制"该x:

x -> (x, x)
x -> (x -> a, x -> b) -> (a, b)
((x, x) -> y) x -> y
(x -> x -> y) -> x -> y
(x -> y) -> (x -> y -> z) -> (x -> z)

这些实际上很难找到; 我想象其中第一个将以名称提供dup x = (x, x),但它无处可寻.据我所知,在序曲中没有任何一个可以找到.

事实证明,有一个称为"读者"monad的Monad x通过许多函数来连接一个值(在这种情况下是你的).这个monad的类型是(->) x,意味着它是x -> y所有人的功能y.上面倒数第二个函数(x -> x -> y) -> x -> y实际上可以写成:

Prelude> :m + Control.Monad
Prelude Control.Monad> :t (id >>=)
(id >>=) :: (a -> a -> b) -> a -> b

因此你可以写:

id >>= (==) . reverse

甚至更简洁:

palindrome = reverse >>= (==)

事实证明,其他人的版本(>>=)在幕后秘密使用.事实证明,例如每个Monad都是一个Applicative,并且Control.Applicative库导出一个符号(<*>) :: Applicative f => f (x -> y) -> f x -> f y.在的情况下,f为(->) a我们:(<*>) :: (a -> x -> y) -> (a -> x) -> y我们可以申请(==)并reverse获得:

palindrome = (==) <*> reverse

或者Control.Monad具有相同instance Monad ((->) x)和出口都>>=为它(如上,(x -> y) -> (y -> x -> z) -> x -> z而join :: m (m x) -> m x在这种情况下是(x -> x -> y) -> x -> y.

有很多选项,但实例声明是在这些库中进行的.如果你想在没有这些库的情况下这样做,你必须写出单调乏味的:

instance Monad ((->) x) where
    return = const
    yx >>= zxy = \x -> zxy (yx x) x

在应用这些功能之前.那时写起来几乎更容易:

Prelude> let dup x = (x, x)
Prelude> let palindrome = uncurry ((==) . reverse) . dup
Prelude> :t palindrome
palindrome :: Eq a => [a] -> Bool

Answer 3

您可以使用join从Control.Monad

palindrome = join ((==) . reverse)

join是monad的基本功能.但是,对于这个特殊情况,它是函数(或更确切地说是(->)实例Monad),join f x只需求值为f x x.