Is there a way to use type-level pattern matching rather than defining a type family

Viewed 64

Consider the following 3 Haskell files

HList.hs

{-# LANGUAGE DataKinds     #-}
{-# LANGUAGE GADTs         #-}
{-# LANGUAGE PolyKinds     #-}
{-# LANGUAGE TypeOperators #-}
module HList where

data HList :: (k -> *) -> [k] -> * where
  Nil :: HList f '[]
  (:&) :: !(f x) -> HList f xr -> HList f (x ': xr)

Snd.hs

{-# LANGUAGE DataKinds           #-}
{-# LANGUAGE KindSignatures      #-}
{-# LANGUAGE RankNTypes          #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TypeFamilies        #-}
{-# LANGUAGE TypeOperators       #-}
module Snd where

import           HList

hmap :: forall f g xs. (forall x. f x -> g x) -> HList f xs -> HList g xs
hmap f = go

  where
    go :: HList f xs' -> HList g xs'
    go Nil       = Nil
    go (x :& xs) = f x :& go xs

type family Snd x where
  Snd '(a, b) = b

type family MapSnd xs where
  MapSnd '[] = '[]
  MapSnd (y ': ys) = Snd y ': MapSnd ys

hmap2 :: forall f g (xs :: [(*,*)]). (forall x. f x -> g (Snd x)) -> HList f xs -> HList g (MapSnd xs)
hmap2 f = go
  where
    go :: HList f xs' -> HList g (MapSnd xs')
    go Nil       = Nil
    go (x :& xs) = f x :& go xs

NoSnd.hs

{-# LANGUAGE DataKinds           #-}
{-# LANGUAGE KindSignatures      #-}
{-# LANGUAGE RankNTypes          #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TypeFamilies        #-}
{-# LANGUAGE TypeOperators       #-}
module NoSnd where

import           HList

hmap :: forall f g xs. (forall x. f x -> g x) -> HList f xs -> HList g xs
hmap f = go
  where
    go :: HList f xs' -> HList g xs'
    go Nil       = Nil
    go (x :& xs) = f x :& go xs

type family MapSnd xs where
  MapSnd '[] = '[]
  MapSnd ('(_, y) ': ys) = y ': MapSnd ys

hmap2 :: forall f g (xs :: [(*,*)]). (forall x a b. (x ~ '(a, b)) => f x -> g b) -> HList f xs -> HList g (MapSnd xs)
hmap2 f = go
  where
    go :: HList f xs' -> HList g (MapSnd xs')
    go Nil       = Nil
    go (x :& xs) = f x :& go xs

Compiling Snd.hs works, but compiling NoSnd.hs gives

NoSnd.hs:27:20: error:
    • Could not deduce: x ~ '(a0, x0) arising from a use of ‘f’
      from the context: xs' ~ (x : xr)
        bound by a pattern with constructor:
                   :& :: forall k (a :: k -> *) (x :: k) (xr :: [k]).
                         a x -> HList a xr -> HList a (x : xr),
                 in an equation for ‘go’
        at NoSnd.hs:27:9-15
      ‘x’ is a rigid type variable bound by
        a pattern with constructor:
          :& :: forall k (a :: k -> *) (x :: k) (xr :: [k]).
                a x -> HList a xr -> HList a (x : xr),
        in an equation for ‘go’
        at NoSnd.hs:27:9
    • In the first argument of ‘(:&)’, namely ‘f x’
      In the expression: f x :& go xs
      In an equation for ‘go’: go (x :& xs) = f x :& go xs
    • Relevant bindings include x :: f x (bound at NoSnd.hs:27:9)

The difference between Snd.hs and NoSnd.hs is that, in the latter, instead of defining a type family Snd, I try to destructure types directly. This happens in two places: the definition of MapSnd and the type of (the parameter to) hmap2.

The two questions are: can someone explain the type error; and is there a way to write hmap2 without defining a Snd type family?

Thank you.

1 Answers

The statement

exists a. x ~ '(a, b)

is slightly stronger than the statement

b ~ Snd x

For example, given

type family Any :: (*, *) where {}

It is valid to conclude

Snd Any ~ Snd Any

But it is not valid to conclude

exists a. Any ~ '(a, Snd Any)

because Any doesn't unify with anything else whatsoever.

You have an HList of things indexed by types of kind (*,*), but you don't know that each element actually has a type of the form '(a,b), so you can't pass a proof of that to the function you're given. Now if you had a less-polymorphic list, where the element type was indexed in a known way, then you could pattern match on the elements to get what you want. But that's not what you have, and it's considerably less general and useful. With your current (working) formulation, the passed function is responsible for working out whatever information it needs to know about the structure of the index. But that's perfectly fine; it's in a much better position to know the structure of f than you are. Take your winnings and go!

Related