Если вам интересны задачи по Хаскелю, то как вам такая задача? В Хаскеле можно определит натуральные числа, как в Пиановской арифметике: data Natural = Zero | S Natural
Легко написать instance Num Natural, instance Ord Natural, instance Show Natural, и т.д.
Фактически такой тип Natural это тип натуральных чисел, записанных в унарной системе. Вообще-то унарная система сильно не эффективна. Тем не менее, как это ни странно, существуют естественные ситуации, когда такое представление чисел оказывается более эффективным! Вот смотрите: Prelude Data.Number.Natural> :t f f :: (Num a, Ord a) => a -> Bool Prelude Data.Number.Natural> f (10^5 :: Natural) True (0.01 secs, 32896040 bytes) Prelude Data.Number.Natural> f (10^5 :: Integer) True (2.44 secs, 1934967184 bytes) Prelude Data.Number.Natural> f (10^5 :: Int) True (2.17 secs, 2094407992 bytes) Prelude Data.Number.Natural>
Задача: придумать такую функцию f, которая работала бы одинаково для натуральных чисел из Natural, Integer и Int (конечно для чисел меньше maxBound::Int), но при этом, она работола бы сильно эффективней для пиановских натуральных чисел, чем для стандартных типов, таких как Integer и Int . При этом функция не должна “жульничать” (например, пытаться определить какой ей тип подсунули и специально работать медленно, если тип не тот). Она должна быть более-менее естественной, чтобы демонстрировать пользу унарной записи в реальной жизни.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
no subject
Date: 2015-11-06 10:32 pm (UTC)В Хаскеле можно определит натуральные числа, как в Пиановской арифметике:
data Natural = Zero | S Natural
Легко написать instance Num Natural, instance Ord Natural, instance Show Natural, и т.д.
Фактически такой тип Natural это тип натуральных чисел, записанных в унарной системе. Вообще-то унарная система сильно не эффективна. Тем не менее, как это ни странно, существуют естественные ситуации, когда такое представление чисел оказывается более эффективным! Вот смотрите:
Prelude Data.Number.Natural> :t f
f :: (Num a, Ord a) => a -> Bool
Prelude Data.Number.Natural> f (10^5 :: Natural)
True
(0.01 secs, 32896040 bytes)
Prelude Data.Number.Natural> f (10^5 :: Integer)
True
(2.44 secs, 1934967184 bytes)
Prelude Data.Number.Natural> f (10^5 :: Int)
True
(2.17 secs, 2094407992 bytes)
Prelude Data.Number.Natural>
Задача: придумать такую функцию f, которая работала бы одинаково для натуральных чисел из Natural, Integer и Int (конечно для чисел меньше maxBound::Int), но при этом, она работола бы сильно эффективней для пиановских натуральных чисел, чем для стандартных типов, таких как Integer и Int . При этом функция не должна “жульничать” (например, пытаться определить какой ей тип подсунули и специально работать медленно, если тип не тот). Она должна быть более-менее естественной, чтобы демонстрировать пользу унарной записи в реальной жизни.