Haskell:两次应用多态函数

Question

我们可以为不同对的f :: a -> b和b实现一个多态函数a。我们怎么才能

twice :: (a -> b) -> a -> c
twice f x = f (f x)

打字检查？也就是说，如何编写一个应用两次多态函数的函数？

有了Rank2Types，我们可以稍微靠近一点，但不完全是这样：

{-# LANGUAGE Rank2Types #-}

twice1 :: (forall a. a -> (m a)) -> b -> (m (m b))
twice1 f = f . f

twice2 :: (forall a. m a -> a) -> m (m b) -> b
twice2 f = f . f

因此，一些多态函数可以应用两次：

\> twice1 (:[]) 1
[[1]]
\> twice2 head [[1]]
1

我们能走得更远吗？

10年前，这个问题是在哈斯克尔咖啡馆提出的。没有得到完全的回答(对于类型类，它变成了大量的样板)。

Answer 1

{-# LANGUAGE TypeFamilies, RankNTypes, UnicodeSyntax #-}

type family Fundep a :: *

type instance Fundep Bool = Int
type instance Fundep Int = String
...

twice :: ∀ a . (∀ c . c -> Fundep c) -> a -> Fundep (Fundep a)
twice f = f . f

现在，这实际上没有多大用处，因为您不能定义一个(有意义的)多态函数，它可以与任何c一起工作。一种可能是抛出类约束，如

class Showy a where
  type Fundep a :: *
  showish :: a -> Fundep a

instance Showy Bool where
  type Fundep Bool = Int
  showish = fromEnum
instance Showy Int where
  type Fundep Int = String
  showish = show

twice :: ∀ a b . (Showy a, b ~ Fundep a, Showy b) =>
    (∀ c . Showy c => c -> Fundep c) -> a -> Fundep b
twice f = f . f

main = print $ twice showish False

Answer 2

即使在依赖类型的设置中，也不能使twice足够通用，但是可以使用交叉类型：

twice :: (a -> b /\ b -> c) -> a -> c
twice f x = f (f x)

现在，无论何时f :: a -> b和f :: b -> c打字机，twice也将打字机。

本杰明·皮尔斯的论文中还有一个漂亮的拼写(我稍微修改了语法)：

self : (A /\ A -> B) -> B
self f = f f

因此，自应用程序也可以与交集类型一起键入。