Класс вариативных функций в Haskell

Функции с переменным числом, конечно, возможны, но «заполнение» нулями немного сложно. Основная причина этого в том, что GHC на самом деле не знает, сколько нужно заполнить! Возьми свою функцию f. Вам может показаться очевидным, что «заполнение нулями» означает применение 0 к f дважды, но вы уверены? Что касается GHC, возможно, вы хотите, чтобы ваш результат был функцией из a -> a. Или, может быть, вы создали у функций типа Int -> Int экземпляр Num — тогда, возможно, fillZeros следует сначала предоставить два аргумента 0 :: Int -> Int для f, а затем еще и 0 :: Int. Есть так много вариантов!

По сути, это сводится к тому, что вы можете создать функцию fillZeros, но вам обязательно понадобятся аннотации типов, чтобы делать с ней что-то полезное. С этой оговоркой приступим.

Хорошая начальная попытка для класса:

{-# LANGUAGE MultiParamTypeClasses #-}

class FillZeroes x y where
  fillZeroes :: x -> y

instance (Num a, FillZeroes b c) => FillZeroes (a -> b) c where
  fillZeroes f = fillZeroes (f 0)

Здесь fillZeroes — это функция, которая принимает x и производит y, и мы создали экземпляр, где x — это тип функции a -> b (где Num a). Обратите внимание, как это выглядит рекурсивно, с ограничением FillZeroes b c и вызовом fillZeroes (f 0) в реализации. Если это рекурсивный случай, то, очевидно, нам понадобится базовый случай. Как мы можем написать это? Самый простой вариант — использовать перекрывающийся экземпляр:

instance {-# OVERLAPPABLE #-} FillZeroes a a where
  fillZeroes = id

Это говорит о том, что если никакие другие экземпляры не применимы (т. Е. Если тип x не является функцией, которая может принимать число), то больше ничего не делайте. Давайте посмотрим, что произойдет (обратите внимание, что удаление аннотации любого типа вызовет ошибку):

{-# LANGUAGE TypeApplications #-}

> fillZeroes (f @Int) :: Int
1
> fillZeroes (f @Int 4) :: Int
5
> fillZeroes (g @Int) :: Int
0
> fillZeroes (h @Int) :: Bool
False

Можем ли мы сделать лучше? Почему нам нужно сообщать GHC как конкретный тип функции (что мы делаем с помощью приложения типа @Int), так и тип результата? Проблема в том, что GHC необходимо точно знать оба типа x и y, чтобы получить правильные экземпляры классов типов. Как оказалось, мы можем использовать семейства типов, чтобы обойти это препятствие. Рассмотрим следующее семейство типов:

{-# LANGUAGE TypeFamilies #-}

type family FZResult a where
  FZResult (a -> b) = FZResult b
  FZResult a = a

Это (закрытое) семейство типов дает тип результата, который мы ищем. Итак, мы можем добавить это в наш класс вместо параметра y:

class FillZeroes a where
  fillZeroes :: a -> FZResult a

instance {-# OVERLAPPABLE #-} FZResult a ~ a => FillZeroes a where
  fillZeroes = id

instance (Num b, FillZeroes a) => FillZeroes (b -> a) where
  fillZeroes f = fillZeroes (f 0)

Теперь нам нужно только сообщить GHC, каков конкретный тип аргумента, и он может использовать семейство типов, чтобы определить, сколько нулей нужно заполнить:

> fillZeroes (f @Int)
1
> fillZeroes (f @Int 4)
5
> fillZeroes (g @Int)
0
> fillZeroes (h @Int)
False