Haskell Int в строку

Я знаю, что этот вопрос возникал раньше, но ответ в этом вопросе по какой-то причине не не работает для меня. Мой пример - следующий код:

fiblist = 0 : 1 : (zipWith (+) fiblist (tail fiblist))

fib :: (Integral a) => a -> String
fib n
  | n < 10000 = show (fiblist !! n)
  | otherwise = error "The number is too high and the calculation might freeze your machine."

Я пытаюсь преобразовать элемент с индексом n в строку, чтобы функция соответствовала его сигнатуре, но получаю следующую ошибку:

MyLib.hs:63:34:
    Couldn't match expected type ‘Int’ with actual type ‘a’
      ‘a’ is a rigid type variable bound by
          the type signature for fib :: Integral a => a -> String
          at MyLib.hs:61:8
    Relevant bindings include
      n :: a (bound at MyLib.hs:62:5)
      fib :: a -> String (bound at MyLib.hs:62:1)
    In the second argument of ‘(!!)’, namely ‘n’
    In the first argument of ‘show’, namely ‘(fiblist !! n)’
Failed, modules loaded: none.

Итак, как я могу преобразовать его?

Изменить №1:

Мне известны параметры командной строки +RTS -M256m -K256m и тому подобное, но они, похоже, не работают для этого кода, он по-прежнему съедает почти всю мою память, если n слишком велико. Другое поведение для length бесконечного списка, там аргументы командной строки работают и останавливают выполнение кода.

Изменить №2:

Я нашел способ импортировать genericIndex:

import Data.List

что, я думаю, совпадает с тем, что показано на здесь.

Теперь, когда я использую следующий код:

fib :: (Integral a) => a -> String
fib n
  | n < 10000 = genericIndex fiblist n
  | otherwise = error "The number is too high and the calculation might freeze your machine."

Я получаю следующую ошибку:

MyLib.hs:64:11:
    No instance for (Num String) arising from the literal ‘0’
    In the first argument of ‘(:)’, namely ‘0’
    In the expression: 0 : 1 : (zipWith (+) fiblist (tail fiblist))
    In an equation for ‘fiblist’:
        fiblist = 0 : 1 : (zipWith (+) fiblist (tail fiblist))
Failed, modules loaded: none.

person Zelphir Kaltstahl    schedule 11.02.2016    source источник
comment
Есть гораздо более быстрые способы выполнения вычислений.   -  person dfeuer    schedule 11.02.2016
comment
@dfeuer вроде оффтоп, но мне интересно. Не могли бы вы связать меня один?   -  person Zelphir Kaltstahl    schedule 11.02.2016
comment
Где-то на вики Haskell есть целая страница путей. Большое ага! один состоит в том, чтобы разбить последовательность на пары (1,1),(2,3),... и понять, что вы можете перейти от каждой пары к следующей путем умножения на ту же матрицу. Затем, поскольку матричное умножение является ассоциативным, вы можете использовать возведение в степень путем возведения в квадрат, чтобы сделать его сверхбыстрым — O (log n) сложений, чтобы получить n-й элемент, если я не очень ошибаюсь.   -  person dfeuer    schedule 11.02.2016
comment
Примечание: вы можете обмануть свой путь к возведению в степень путем возведения в квадрат, создав фиктивный экземпляр Num для вашего типа матрицы, поддерживающий только умножение и fromInteger (что должно давать диагональные матрицы). Это позволит вам использовать ^, который в GHC, по крайней мере, использует возведение в степень путем возведения в квадрат.   -  person dfeuer    schedule 11.02.2016
comment
@dfeuer Звучит довольно сложно. И тут я подумал, что нашел хорошее и эффективное решение :D   -  person Zelphir Kaltstahl    schedule 11.02.2016
comment
Не так уж и сложно, на самом деле. См. wiki.haskell.org/.   -  person dfeuer    schedule 11.02.2016


Ответы (1)


Поскольку вы утверждаете, что fib является полиморфным для всех экземпляров Integral, самое простое решение, вероятно, состоит в том, чтобы переключиться с использования (!!) на использование genericIndex, которые имеют следующие сигнатуры типов:

(!!)         ::               [a] -> Int -> a
genericIndex :: Integral i => [a] ->  i  -> a
person Daniel Wagner    schedule 11.02.2016
comment
Обновил мой вопрос. - person Zelphir Kaltstahl; 11.02.2016
comment
@Zelphir Вы изменили (!!) на genericIndex, но по какой-то причине удалили show! - person Daniel Wagner; 11.02.2016