Список длины Хаскеля + факториал

Question

Я очень новичок в Хаскеле. Я пытался реализовать n_choose_r, но по какой-то причине моя факторная функция возвращает странные значения.

Main.hs

factorial 0 = 1
factorial n = n * factorial (n-1)

subsets k list = factorial n where
    n = length list

некоторые другие случаи

> subsets 3 [1..4]
24 // correct value
> factorial 60
8320987112741390144276341183223364380754172606361245952449277696409600000000000000
> subsets 3 [1..60]
-8718968878589280256 // wrong value
> subsets 3 [1..100]
0 // wrong value

Кажется, что чем длиннее список, тем выигрывают цифры. Кто-нибудь может объяснить?

Answer 1

Ваша factorial функция полиморфна: она имеет тип (Eq p, Num p) => p -> p. Когда вы просто называете это как factorial 60, p создается как Integer (этот выбор называется «тип по умолчанию»), что имеет произвольную точность и не имеет верхней границы. Однако length не является полиморфным в своем выводе: он всегда возвращает Int. Haskell не будет автоматически конвертировать числовые типы для вас, поэтому, когда вы вызываете factorial с результатом length, он также использует Int, который имеет верхнюю границу, которая в вашем случае выглядит как 9223372036854775807 (что вы можете проверить, выполнив maxBound :: Int). Чтобы обойти эту проблему, вы можете либо самостоятельно преобразовать Int в Integer:

subsets k list = factorial (toInteger n) where
    n = length list

, либо использовать genericLength, что совпадает с length, за исключением того, что он полиморфен в своем выводевведите:

import Data.List

subsets k list = factorial n where
    n = genericLength list

Обратите внимание, что если вы используете последний вариант, вы должны быть осторожны, чтобы не делать ничего другого, что заставило бы использовать Int вместо значения по умолчанию Integer.