Haskell: digitToInt + show быстрее численной реализации

[user14284]

Пусть digit -- функция, преобразующую число Integer в список его десятичных цифр [Int] (порядок не важен).

Вопрос. Почему такое решение, с промежуточным преобразованием числа в строку,

import Data.Char (digitToInt)
digits :: Integer -> [Int]
digits = map digitToInt . show

работает примерно в 2 раза быстрее, чем непосредственное численное вычисление

digits :: Integer -> [Int]
digits 0 = []
digits n = let (q, r) = quotRem n 10 in (fromIntegral r) : (digits q)

И в GHCI и при компиляции через ghc -O.

[Eimrine]

Потому, что итерация map-а занимает заметно меньше времени, чем итерация с побитовым сдвигом, разве вывод не очевиден?

[arseniiv]

Вместо того чтобы делать предположения, стоит открыть исходный код инстанса Show Integer и посмотреть методы: http://hackage.haskell.org/package/base-4.9.0.0/docs/src/GHC.Show.html#line-437.

-- Пн окт 24, 2016 01:13:04 --

user14284
Кстати, попробуйте переписать вашу версию с использованием unfoldr.

-- Пн окт 24, 2016 01:21:09 --

И ещё можно попробовать заменить quotRem на divMod, раз уж у вас с отрицательными числами всё равно проблемы в обоих вариантах.

[user14284]

Eimrine
А как, по-вашему, show работает?

arseniiv в сообщении #1162382 писал(а):

Вместо того чтобы делать предположения, стоит открыть исходный код инстанса Show Integer и посмотреть методы:

Посмотрел, то же через quotRem реализовано (да и а как иначе)?

arseniiv в сообщении #1162382 писал(а):

И ещё можно попробовать заменить quotRem на divMod, раз уж у вас с отрицательными числами всё равно проблемы в обоих вариантах

Так divMod определяется через quotRem.

[arseniiv]

Хм, что-то я тут насоветовал, а сам не посмотрел. Почему-то казалось, что divMod должен быть базовым.

-- Пн окт 24, 2016 07:47:49 --

user14284 в сообщении #1162451 писал(а):

Посмотрел, то же через quotRem реализовано (да и а как иначе)?

Там ещё оптимизация (недаром такая куча кода вместо простой вашей строки). В детали не вчитывался.

Про развёртку я тоже на авось написал. Разве что для интереса, как выглядеть будет.

-- Пн окт 24, 2016 07:54:07 --

Кстати, совсем уж шутки ради попробуйте не делать fromIntegral, получая список Integerов. Просто для сравнения.

P. S. Ещё я нашёл модуль Data.Digits из пакета digits, но там тоже как у вас, только основание любое, и зачем-то позволительно основание 1, которое вообще-то от другого вида позиционной системы. (Ну да ладно, этот вид заблуждений — особь статья.)

-- Пн окт 24, 2016 08:11:28 --

user14284 в сообщении #1162451 писал(а):

Так divMod определяется через quotRem.

Я таки глянул в код. В инстансах всё-таки вижу отдельные примитивы для всех div, mod, quot, rem, divMod, quotRem (и это правильно), а в классе странно, что предпоследнее определяется с помощью последнего, а наоборот не сделали. (Класс Eq прекрасно живёт с «циклическими» определениями (потому что до этого при определении инстанса дело не дойдёт — компилятор обязует нас определить хотя бы == или /=, потому что ему указали, какие минимальные полные определения позволять.)