Есть ли практический способ использования натуральных чисел в Haskell? - PullRequest
Новая
       39

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

24 голосов
/ 30 июля 2011

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

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

data Nat = Zero | Succ Nat

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

Поэтому я спрашиваю, есть лиспособ сделать это?(что похоже на использование «unsigned» в C)

Заранее спасибо.

РЕДАКТИРОВАТЬ: Я собираюсь скрыть этовнутри модуля, как объяснил CA McCann.Также я должен добавить следующую ссылку: http://haskell.org/haskellwiki/Smart_constructors для краткого изложения по теме.Спасибо, что нашли время ответить!

Ответы [ 3 ]

19 голосов
/ 30 июля 2011

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

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

Абстрактный тип данных - это тип, который определен в отдельном модуле и не экспортирует его конструкторы, например 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 экземпляра , потому что он успешно нарушит ваше неотрицательное ограничение.

9 голосов
/ 30 июля 2011

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

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

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 голосов
/ 04 августа 2011

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

имеется версия .
...