This post is an exploration of a generic technique to effectively circumvent return type polymorphism in Haskell programs using GADTs and existential quantification.

This was already featured in the Weekly News a couple of weeks back, but I think maybe it deserves it’s own thread. I’ve tried to explain this approach to some people before, but I think this article does a much better job than I have.

I do think the “Defeating” in the title might be a little bit negative, it’s have preferred something neutral like “When your result type depends on your argument values”, but it’s still something useful to know from retaining your type safety.

This existentials and GADTs can be converted into a CPS style without type equality constraints (usually, with enough work) so that you can start from this description but use it in languages with less sophisticated type systems – as long as they have parametricity – like Haskell 2010.

  • jaror@kbin.social
    2·
    1 year ago

    The Lemmy->Kbin conversion has inserted a lot of <span> elements into your code making it unreadable. For people reading this from the Kbin side, here’s the code:

    {-# language GADTs #-}
{-# language RankNTypes #-}

import Data.Functor.Const

-- The GADT
data AGADT a where
    I :: [Integer] -> AGADT Integer
    S :: String -> AGADT String

type Scott_GADT a = forall fr. ([Integer] -> fr Integer) -> (String -> fr String) -> fr a

f :: AGADT a -> String
f (I x) = show x
f (S x) = x

f' :: Scott_GADT a -> String
f' x = getConst $ x (Const . show) Const

-- The Existential
data AnyGADT = forall a. MkAnyGADT (AGADT a)

type Scott_Any =
  forall r.
    (forall a. (forall fr. ([Integer] -> fr Integer) -> (String -> fr String) -> fr a) -> r) ->
    r

g :: String -> AnyGADT
g "foo" = MkAnyGADT (I [42])
g "bar" = MkAnyGADT (I [69])
g x = MkAnyGADT (S x)

g' :: String -> Scott_Any
g' "foo" x = x (\i _s -> i [42])
g' "bar" x = x (\i _s -> i [69])
g' s x = x (\_i s' -> s' s)

main = interact (unlines . fmap x . lines)
 where
  x s = case g s of { MkAnyGADT x -> f x }
  y s = g' s f'

```</span>
    • bss03OP
      2·
      1 year ago

      I think the spans are all syntax highlighting/coloring. Your comment seems to have a dangling ```/span at the end to me, but that might just be the KBin->Lemmy translation.

      EDIT: Also, Lemmy seems to be munging this post between the preview and the submit, due to me wanting to include some text that appears to be a dangling xml/html end tag (angle brackets removed in edit for “readability”) inside backticks.