Существует ли практический способ использования натуральных чисел в Haskell?

Я изучаю Haskell и хотел бы навязывать использование положительных целых чисел (1,2,3,...) в некоторых конструкторах, но я только, кажется, нахожу типы данных "Int" и "Integer".

Я мог бы использовать канонический

data Nat = Zero | Succ Nat

но тогда я не мог использовать 1, 4,... для их обозначения.

Итак, я спрашиваю, есть ли способ сделать это? (что похоже на использование "unsigned" в C)

Спасибо заранее.

EDIT: Я собираюсь спрятать его внутри модуля, как объяснил К. А. Макканн. Кроме того, я должен добавить следующую ссылку: http://haskell.org/haskellwiki/Smart_constructors для резюме по этому вопросу. Спасибо, что нашли время ответить!

Ответы

Ответ 1

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

Заметим, что индуктивное представление не очень эффективно для больших чисел; однако он может быть ленивым, что позволяет вам делать такие вещи, как видеть, какая из двух nats больше, не оценивая больше, чем размер меньшего.

Абстрактный тип данных - это тот, который определен в отдельном модуле и не экспортирует его конструкторы, примеры IO или Data.Set.Set. Вы можете определить что-то вроде этого:

module Nat (Nat() {- etc. -} ) where

newtype Nat = Nat { unNat :: Integer }

... где вы экспортируете различные операции на Nat, так что, хотя внутреннее представление просто Integer, вы гарантируете, что значение типа Nat не построено с отрицательным значением.

В обоих случаях, если вы хотите использовать числовые литералы, вам понадобится определение fromInteger, которое привязано к классу типа Num, что совершенно неверно для натуральных чисел, но хорошо.

Если вы не возражаете сделать сломанный экземпляр, чтобы получить синтаксические тонкости, вы можете сделать что-то вроде этого:

instance Num Nat where
    Zero + n = n
    n + Zero = n
    (Succ n1) + (Succ n2) = Succ . Succ $ n1 + n2

    fromInteger 0 = Zero
    fromInteger i | i > 0 = Succ . fromInteger $ i - 1

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

Ответ 2

Вы можете использовать Word32 из Data.Word, что соответствует uint32_t в C.

С Word32 вы получаете те же проблемы, что и с неподписанными типами в C, особенно over- и underflow. Если вы хотите убедиться, что этого не произойдет, вам нужно привязать его к новому типу и только экспортировать интеллектуальный конструктор. Таким образом, никакое сложение, вычитание и т.д. Не было бы возможным, и не было бы риска чрезмерного или недостаточного. Если вы хотите поддержать добавление, например, вы можете добавить и экспортировать функцию для добавления неподписанных ints, но с проверкой на переполнение (и с ограничением производительности). Он может выглядеть следующим образом:

module NT(UInt, addUInts) where

import Data.Word

newtype UInt = UInt Word32
  deriving (Show)

mkUInt :: Word32 -> UInt
mkUInt = UInt

addUInts :: UInt -> UInt -> Maybe UInt
addUInts (UInt u1) (UInt u2) =
  let u64 :: Word64
      u64 = fromIntegral u1 + fromIntegral u2
  in if u64 > fromIntegral (maxBound :: Word32)
       then Nothing
       else Just (UInt (fromIntegral u64))

Ответ 3

Я не могу вспомнить, относится ли это к вашему конкретному вопросу, но вам может понравиться статья Колина Рунсимана А как насчет натуральных чисел?. В случае, если вы не можете преодолеть платный сервер, на Citeseer существует .