Geek asks and answers

The need for an existential type

It turns out that it is surprisingly difficult to use existential / rank-n types, despite the very simple idea behind them.

Why are there existential types of flow around types data?

I have the following simple example:

{-# LANGUAGE RankNTypes, ImpredicativeTypes, ExistentialQuantification #-}
module Main where

c :: Double
c = 3

-- Moving `forall` clause from here to the front of the type tuple does not help,
-- error is the same
lists :: [(Int, forall a. Show a => Int -> a)]
lists = [ (1, \x -> x)
        , (2, \x -> show x)
        , (3, \x -> c^x)
        ]

data HRF = forall a. Show a => HRF (Int -> a)

lists' :: [(Int, HRF)]
lists' = [ (1, HRF $ \x -> x)
         , (2, HRF $ \x -> show x)
         , (3, HRF $ \x -> c^x)
         ]

If I comment on the definition lists, the code compiles successfully. If I do not comment on this, I get the following errors:

test.hs:8:21:
    Could not deduce (a ~ Int)
    from the context (Show a)
      bound by a type expected by the context: Show a => Int -> a
      at test.hs:8:11-22
      `a' is a rigid type variable bound by
          a type expected by the context: Show a => Int -> a at test.hs:8:11
    In the expression: x
    In the expression: \ x -> x
    In the expression: (1, \ x -> x)

test.hs:9:21:
    Could not deduce (a ~ [Char])
    from the context (Show a)
      bound by a type expected by the context: Show a => Int -> a
      at test.hs:9:11-27
      `a' is a rigid type variable bound by
          a type expected by the context: Show a => Int -> a at test.hs:9:11
    In the return type of a call of `show'
    In the expression: show x
    In the expression: \ x -> show x

test.hs:10:21:
    Could not deduce (a ~ Double)
    from the context (Show a)
      bound by a type expected by the context: Show a => Int -> a
      at test.hs:10:11-24
      `a' is a rigid type variable bound by
          a type expected by the context: Show a => Int -> a at test.hs:10:11
    In the first argument of `(^)', namely `c'
    In the expression: c ^ x
    In the expression: \ x -> c ^ x
Failed, modules loaded: none.

Why is this happening? Should the second example not coincide with the first? What is the difference between these custom n-rank types? Is it possible to completely abandon the additional definition of ADT and use only simple types when I want such polymorphism?

+5
source share
3 answers

, :

  • ", show n", , , .
  • .

, , :

data Showable = Show a => Showable a

, - :

data Showable a = Showable (instance of Show a) a

.. Show a a. , Showable, , a.

-, let, .

. , forall a . Show a => (Int -> a), , , , , . , exists a . Show a => (Int -> a), , , , show.

+3

. ,

lists :: [(Int, forall a. Show a => Int -> a)]

, , , - , .

lists :: [(Int, exists a. Show a * (Int -> a))]  -- not real Haskell

, . exists forall .

HRF :: forall a. Show a => (Int -> a) -> HRF

, HRF , a, a Show Show a Int -> a. HRF -

HRF :: (exists a. Show a * (Int -> a)) -> HRF   -- not real Haskell

, , rank-n Church-encode

type HRF = forall x. (forall a. Show a => (Int -> a) -> x) -> x

, , .

+6

. ,

lists :: [(Int, forall a. Show a => Int -> a)]

, , Show Int.

- ,

lists :: [(Int, exists a. Show a => Int -> a)]

i., every second component can infer some type belonging Showto from Int, but you do not know what type this function returns.

In addition, the functions that you enter in the tuples do not satisfy the first contract:

lists = [ (1, \x -> x)
        , (2, \x -> show x)
        , (3, \x -> c^x)
        ]

\x -> xcreates the same type as the result that it is entered as input, so here Int. Showalways creates String, therefore one fixed type. finally \x -> c^xproduces the same type cas, namely Double.

+3
source

More articles:


All Articles