Alexander
[] - whnf, и (:) _ _ - whnf
Alexander
(Да можно с помощью ! создавать зависимости по данным, но к этому вернёмся позже)
Alexander
(:) _ _
Alexander
где под _ невычисленное ещё значение
Alexander
далее я буду писать его как <_:само выражение>
Alexander
т.е. (:) <_:'h'> <_:(:) <_:'e'> <_:[]>> в этих терминах
Alexander
Если с этим согласен то можно будет посмотреть на то, как работает foldl'
Alexander
Давай посмотрим
Alexander
Первые 2 шага, сначала ленивый:
первый шаг:
аккумулятор: [],
значение в списке пусть <_:"x">
мы возвращаем: <_: [] ++ "x">
второй шаг:
аккумулятор: <_: [] ++ "x">
значение в списке путь <_:"y">
возвращаем: <_: <_: [] ++ "x"> ++ <_:"y">>
Ilya
Так, тут накапливается thunk thunk'ов
Alexander
Теперь посмотрим строгий:
аккумулятор: [],
значение в списке пусть <_:"x">
т.е. мы форсим аккумулятор, то он вычисляется до []
итого мы возвращаем: <_: [] ++ "x">
пока все так же, смотрим второй шаг:
аккумулятор: <_: [] ++ <_:"x">>
значение в списке путь <_:"y">
но мы форсим аккумулятор до WHNF, а у нас не WNNF, итого мы должны вычислять
[] ++ <_:"x"> по определению [] ++ x = x, итого у нас <_:"x">
но это не whnf, вычислям дальше, получаем: <_:'x'>:<_:[]>
это WHNF итого возвращаем:
<_:<_:'x'>:<_:[]> ++ <_:"y">>
это лучше, чем раньше, но все равно вычисленным у нас будет только самый внешний конструктор и мы накопим кучу санков
Alexander
Т.е. поэтому я сказал, что foldl' тут не поможет
Alexander
Причина в том, что foldl' поможет только в том случае, если ты работаешь с WHNF-строгой структурой, т.е. такой структурой для которой WHNF=NF
Alexander
например если бы у нас были числа
Alexander
то вместо foldl (+) 0 [1,2] = foldl (+) (0 + 1) [2] = <_:<_:0+1> + 2> получишь уже:
foldl' (+) 0 [1,2] = foldl' (+) 1 [2] = <_:1+2>
ну или даже 3 (я не помню, как там сделана зависимость)
Alexander
Т.о. foldl' помогает для WNHF-strict структур, а foldl плох вообще всегда
Alexander
И если для строк этого ещё как-то ожидаешь, но для пар уже реже и это приводило к ошибкам у многих людей
Alexander
пакеты типа foldl сильно решают эту проблему
Alexander
Это понятно?
Ilya
Теперь посмотрим строгий:
аккумулятор: [],
значение в списке пусть <_:"x">
т.е. мы форсим аккумулятор, то он вычисляется до []
итого мы возвращаем: <_: [] ++ "x">
пока все так же, смотрим второй шаг:
аккумулятор: <_: [] ++ <_:"x">>
значение в списке путь <_:"y">
но мы форсим аккумулятор до WHNF, а у нас не WNNF, итого мы должны вычислять
[] ++ <_:"x"> по определению [] ++ x = x, итого у нас <_:"x">
но это не whnf, вычислям дальше, получаем: <_:'x'>:<_:[]>
это WHNF итого возвращаем:
<_:<_:'x'>:<_:[]> ++ <_:"y">>
это лучше, чем раньше, но все равно вычисленным у нас будет только самый внешний конструктор и мы накопим кучу санков
Ага.. Ясно.
А какие ошибки с парами были?
Alexander
Тоже самое whnf пары не вычисляет поля
Alexander
скажем foldl' (\(count, sum) x -> (count+1, sum+x)) накопит кучу санков
Alexander
И для того, чтобы это решить (не используя специальных пакетов нужно или сделать строгую пару (правильный путь) :
data SP a b = SP !a !b
Alexander
Тут та же гарантия, что в. ыуйб если структура вычислена до WHNF (конструктора SP) то поля тоже вычислены до WHNF
Alexander
т.е. создается зависимость по данным
Ilya
А вот эта нотация с ! доступна без сторонних пакетов?
Alexander
Или тоже самое, но вручную в теле функции:
foldl' (\(count, sum) x -> let count' = count+1; sum'=sum+x in count' seq sum' seq (count', sum')
Alexander
Да
Зигохистоморфный
Denis
надо bang patterns
Alexander
Вот для let !count' = count+1 ; !sum' = sum+x in (count', sum') не надо
Alexander
А для \(!count, !sum) - надо
Alexander
Впрочем не важно компилятор если надо скажет
Alexander
Если с этим разобрались, то ещё к foldr надо будет вернуться
Ilya
Alexander
Никак - использовать вектор, скажем
Alexander
Или итеративную структуру какую
Alexander
Можно свой список строгий заделать SL = [] | SL !a !(SL a)
Alexander
Но это такое себе удовольствие, куча функций с ним резко начнёт плохо работать
Alexander
Для этого давай про foldr поговорим
A64m
Ilya
Для этого давай про foldr поговорим
Тут, на первый взгляд, все ясно. У нас есть операция, для которогой один из аргументов известен, а другой — это foldr по всему списку, кроме последнего аргумента, т. е. тут никуда не денешься, придется строить thunk. Так?
Alexander
Alexander
Ты что-то не то делаешь
Alexander
Причем в старом компиляторе
Alexander
A64m
Alexander
Давай запишем, какой-нибудь foldr
Cheese
Alexander
foldr <+> 0 [1,2,3] = 0 <+> (1 <+> (2 ...)
Ilya
Так
Alexander
Лень спорить, если честно и проверять
Alexander
Про foldr интереснее
A64m
где-то в кабал файле есть значит
A64m
без прагмы только в объявлении произведения работает
Alexander
Так
Так вот если функция <+> ленивая по второму аргументу, то мы строим результат:
0 <+> (foldr <+> ...)
Alexander
т.е мы не вычисляем его полностью, а сразу же возвращаем выше
Alexander
И продолжение вычисления происходит только тогда, когда тот, кто потребляет результат доходит до невычисленной части структуры
Alexander
это на самом деле именно то, что вам нужно, вам нужно сразу вернуть первый кусок строки, и "описание" того, как достроить хвост
Alexander
Т.о. благодаря тому, что вы строите thunk, вы их не копите и не производите все вычисление до тех пор, пока этого не потребуется
Alexander
Как раз благодаря тому, что список ленивый
Cheese
У меня в 8.4 позволяло не добавляя
я тоже не хочу спорить, просто делюсь своими и впитываю твои наблюдения. без расширений, кстати, можно strict pair объявить и матчить по нему
Alexander
Это было предложено как первый и правильный вариант
Ilya
Alexander
в 8.6 действительно не сработало, может в 8.4 были ошибки и до этого сообщения тупо не дошло
Alexander
((((...(1+2)+...)+k)+...) vs 1+(2+(....)
Alexander
второе ты можешь потреблять строя только 1 уровень отложенных вычислений
Alexander
а первое только построив все
Alexander
Потреблять = вычислять
Alexander
уровень - количество вложенных
Alexander
Мы можем хотеть все и сразу, а можем по частям