CODEWITHSUNDEEP
haskell
behzad.nouri
behzad.nouri

Reputation: 77941

Haskell: apply a polymorphic function twice

We can have a polymorphic function f :: a -> b implemented for different pairs of a and b. How can we make

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

type check? i.e. how can I write a function which applies a polymorphic function twice?

With Rank2Types we can get a bit closer but not quite there:

{-# 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

so then some polymorphic functions can be applied twice:

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

Can we go further?

The question was asked over Haskell cafe 10 years ago but wasn't quite answered (with type classes it becomes a lot of boilerplate).

Upvotes: 5

Views: 591

Answers (2)

effectfully
effectfully

Reputation: 12715

You can't make twice generic enough even in a dependently typed setting, but it's possible with intersection types:

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

Now whenever f :: a -> b and f :: b -> c typecheck, twice will typecheck too.

There is also a beautiful spell in Benjamin Pierce's thesis (I changed the syntax slightly):

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

So self-application is typeable with intersection types as well.

Upvotes: 4

leftaroundabout
leftaroundabout

Reputation: 120711

{-# 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

Now, that won't be much use actually because you can't define a (meaningful) polymorphic function that works with any c. One possibility is to toss in a class constraint, like

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

Upvotes: 4

Related Questions