Haskell: применять полиморфную функцию дважды

Question

Мы можем иметь полиморфную функцию f :: a -> b, реализованную для разных пар a и b. Как мы можем сделать

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

тип проверка? то есть как я могу написать функцию, которая применяет функцию polyorphic?

С 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 

Можем ли мы пойти дальше?

The question was asked over Haskell cafe10 лет назад, но на него не ответили (с классами типов это становится много шаблонов).

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 typecheck, twice будет typecheck тоже.

Существует также прекрасное заклинание Benjamin Pierce's thesis (я немного изменил синтаксис):

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

Так само-приложение печатаемые с типами пересечений, а также.