如何在Haskell中编写"两次"函数？

Question

我想写'两次'函数,它接受一个函数和一个参数并将该函数应用两次.但是它接收的函数应该对union类型起作用.

例如.

    f a -> b 
    f b -> c

产量

   twice f a
 c
   f a
   b
   f b 
   c
   f c
   error

例如.

f :: Int -> String
f :: String -> Char
twice f :: Int -> Cha

我如何编写带有两种类型的f和执行传递性事物的"两次".

Answer 1

你真的在这里问两件事:"我该如何编写这个函数twice？","我怎么f用两种不同的类型写一个？"

让我们考虑第一个问题.让Haskell暂时推断类型,让我们考虑它应该是什么样子.它需要一个论点:twice f = undefined. twice然后返回一个函数,该函数接受一个参数并应用于f它两次:twice f = \x -> f (f x).

但是这个功能的类型是什么？好吧,x必须是某种类型?.自从我们评估以来(f x),这意味着f必须是一个接受?并返回?:的函数f :: ? -> ?.但是,我们也评估f (f x),所以f必须?作为输入,返回?:f :: ? -> ?.任何单变量只能有一种类型,所以这告诉我们? -> ? = ? -> ?,等? = ?和? = ?.因此,f :: ? -> ?等等\x -> f (f x) :: ? -> ?; 这意味着twice :: (? -> ?) -> ? -> ?.

这回答了你的第一个问题.你会注意到我上面说的f必须是从一种类型到同一种类型的函数.这回答了你的第二个问题:f用两种不同的类型写一个是不可能的.这是因为,正如我所说,任何单个变量可能只有一个(可能是多态)类型.为什么？那么,除其他原因外,假设我们有一个变量impossible有两个类型签名,impossible :: Int并impossible :: String和两个绑定,impossible = 24和impossible = "absz".然后show impossible返回什么？的show功能的类型的show :: Show ? => ? -> String; 因为这两个Int和String是的实例Show类型类,我们不能告诉这是否会返回"42"或"\"absz\"".像这样的不一致是我们只允许一种类型的原因.

然而,所有希望都不会丢失!您还提到了使用联合类型来实现f.在这种情况下,您可能意味着Either类型(尽管Haskell中的所有数据类型都是一种称为区分联合的联合类型). Either是一个带有两个类型参数的类型(就像[]列表类型一样); 我们说它有类型 [类型] Either :: * -> * -> *). Either是联合类型:Either A B由所有元素A和所有元素B组成Either.正如迈克尔斯蒂尔所说,你可以用两种类型的签名编写你的函数,作为一个返回Either值的函数:f :: Either ? ? -> Either ? ?.请注意,这是一个完全有效的值,可以作为参数传递twice,因为Either ? ?它是完全合法的类型.我们在Eithervia模式匹配上定义函数; 两个构造函数Either是Left :: ? -> Either ? ?和Right :: ? -> Either ? ?,用于解除两种类型的值.然后,示例函数看起来像

f :: Either Int String -> Either Int String
f (Left  n) = Right $ "The number " ++ show n
f (Right s) = Left  $ length s

-- f (Left 3)               == Right "The number 3"
-- f (Right "The number 3") == Left 12
-- twice f (Left 3)         == Left 12

如果你真的想模仿你的例子并经历三种类型,从?to ?到to ?,你可以使用嵌套的Eithers或定义你自己的数据类型.使用嵌套的Eithers,你得到

f :: Either Int (Either String Char) -> Either Int (Either String Char)
f (Left  n)         = Right $ Left  $ "The number " ++ show n
f (Right (Left  s)) = Right $ Right $ head $ drop 11 s
f (Right (Right c)) = Left  $ fromEnum c

-- f (Left 42)                      == Right (Left "The number 42")
-- f (Right (Left "The number 42")) == Right (Right '4')
-- f (Right (Right '4'))            == Left 52
-- twice f (Left 42)                == Right (Right '4')

使用新类型,您将获得:

data Either3 a b c = Left3 a | Mid3 b | Right3 c deriving (Eq, Ord, Read, Show)

f :: Either3 Int String Char -> Either3 Int String Char
f (Left3  n) = Mid3   $ "The number " ++ show n
f (Mid3   s) = Right3 $ head $ drop 11 s
f (Right3 c) = Left3  $ fromEnum c

-- f (Left3 42)             == Mid3 "The number 42"
-- f (Mid3 "The number 42") == Right3 '4'
-- f (Right3 '4')           == Left3 52
-- twice f (Left3 42)       == Right3 '4'

你也可以定义一个特定的data MyType = MyInt Int | MyStr String | MyChar Char,并且每更换Either3 Int String Char用MyType,每次Left3用MyInt,每次Mid3用MyStr,每Right3用MyChar; 这实际上是相同的,但不太通用.

请注意,由于Haskell的currying,我们可以将原始内容重写twice为twice f x = f (f x).事实上,更简单地说,我们可以将其写为twice f = f (.) f,或者twice = join (.),如果我们导入Control.Monad.这与回答这个问题的目的无关,但是由于其他原因(特别是我不完全理解的(->) ?实例)很有意思Monad; 你可能想看看你以前没看过它.

Answer 2

您的传递性内容通常称为功能组合,可通过.操作员获得.

f . g = \x -> f(g x)

Twice相反是自组合(函数迭代)的一个例子,你可以表达f . f.

但请注意,Haskell中没有重载函数 - 一个作用域中的每个函数都只有一种类型和实现(尽管这种类型可能是多态的).

Answer 3

这样的twice功能如下所示：

twice :: (a -> a) -> a -> a
twice f = f . f

假设您有一个名为的函数sayIt，可将Int值转换为英语。

sayIt :: Int -> String
sayIt 1 = "One"
sayIt _ = "I don't know!"

无法使该twice函数与sayIt以下代码一起使用：

*Main> sayIt (sayIt 1)

<interactive>:1:7:
    Couldn't match expected type `Int' against inferred type `String'
    In the first argument of `sayIt', namely `(sayIt 1)'
    In the expression: sayIt (sayIt 1)
    In the definition of `it': it = sayIt (sayIt 1)
*Main> twice sayIt 1

<interactive>:1:6:
    Couldn't match expected type `Int' against inferred type `String'
    In the first argument of `twice', namely `sayIt'
    In the expression: twice sayIt 1
    In the definition of `it': it = twice sayIt 1

sayIt仅使用Int值，因此第二次使用String值调用是错误的。

联合类型

您只能将其twice用于接受和返回相同类型的函数。由于您询问了“联合”类型，因此下面是此类函数的示例：

sayIt2 :: Either Int String -> Either Int String
sayIt2 (Left 1)    = Right "One"
sayIt2 (Right str) = Right str
sayIt2 _           = Right "I don't know!"

例：

*Main> twice sayIt2 (Left 1)
Right "One"
*Main> twice sayIt2 (Left 2)
Right "I don't know!"
*Main> twice sayIt2 (Right "Hello")
Right "Hello"