Компилировать ограниченные по времени конечные списки

Question

Я хотел бы создать тип, представляющий списки с конечным числом элементов.

Теперь наивный способ сделать это со строгой оценкой:

data FiniteList a
  = Nil
  | Cons a !(List a)

С этим бесконечным списки эквивалентны основанию.

Однако я хочу тип, который вообще запрещает создание таких списков. В идеале я хотел бы, чтобы любые попытки создать бесконечный список приводили к ошибке времени компиляции.

Я могу начать видеть, как это можно сделать, если я строю списки размеров с использованием GADTs и DataKinds.

data Natural = Zero | Succ Natural

data DependentList :: Natural -> Type -> Type where
  Nil  :: DependentList 'Zero a
  Cons :: a -> DependentList n a -> DependentList ('Succ n) a

Если мы попытаемся создать что-то вроде

a = Cons 1 a

Мы получим ошибку типа, поскольку для этого требуется тип n ~ 'Succ n.

Проблема в том, что это не один тип списка, а скорее класс типов, по одному для каждого размера списка. Так, например, если бы я хотел написать версию take или drop в этом списке, мне нужно было бы заняться серьезной зависимой типизацией.

Я хотел бы объединить все эти отдельные типы в единственный тип, который все еще обеспечивает конечность во время компиляции.

Можно ли это сделать?

Answer 1

Это можно сделать с помощью Liquid Haskell, который обеспечивает проверку завершения.
Типовые сигнатуры выглядят следующим образом в Liquid Haskell:

{-@ (function name) :: (refinement) [/ (termination metric)] @-}

Метрика завершения c является целым числом вектор, который должен уменьшать каждый рекурсивный вызов (лексикографический порядок). Если не указано, LH будет использовать первый целочисленный аргумент в качестве метрики завершения c.
Проверка завершения может быть отключена с помощью отложенной аннотации {-@ lazy (function name) @-}:

{-@ lazy inf @-}
inf x = x : inf x

Answer 2

Да, просто используйте экзисторию, чтобы потом забыть конечную длину:

data NonDependentList a where NonDependentList :: DependentList n a -> NonDependentList a

Конечно, take и drop будут иметь некоторый шаблон ...

take :: Int -> NDL a -> NDL a
take n (NDL Nil) = NDL Nil
take n (NDL (Cons a as)) = case take (n-1) (NDL as) of
    NDL as' -> NDL (Cons a as')

Но вы все еще не можете сделать бесконечным:

ones = NDL (Cons 1 (case ones of NDL os -> os)) -- existential escapes its scope

Answer 3

Существует также подход "Призраки умерших доказательств" , который включает в себя помеченный новый тип с тщательно продуманными умными конструкторами и работу в стиле передачи продолжения с продолжением polymorphi c в теге типа:

{-# LANGUAGE DeriveFunctor, RankNTypes, RoleAnnotations #-} 
module FinList (FinList,empty,toFinList,cons) where 
-- FinList constructor should NOT be public, or else everything breaks!

newtype FinList name a = FinList { getFinList :: [a] } deriving Functor

-- Don't allow Data.Coerce.coerce to turn FinList X a into forall x. FinList x a
type role FinList nominal representational

empty :: forall a r. (forall name . FinList name a -> r) -> r
empty f = f (FinList [])

toFinList:: forall a r. Int -> [a] -> (forall name. FinList name a -> r) -> r
toFinList n as f = f (FinList (take n as))

cons :: forall a r name'. a -> FinList name' a -> (forall name. FinList name a -> r) -> r
cons a (FinList as) f = f (FinList (a:as))

Это должно помешать клиентам модуля FinList создавать циклические определения.