Data.List.inits is not lazy

[sassa_nf]

так и задумано, что ли?

а чо не так:

inits xs = [] : inits' xs where
  inits' xs = case xs of
                [] -> []
                x: xs' -> [x]: (map (x :) $ inits' xs')

Пример:

import Data.List hiding (unfoldr, inits)

inits xs = [] : inits' xs where
  inits' xs = case xs of
                [] -> []
                x: xs' -> [x]: (map (x :) $ inits' xs')

ext :: ([b]->a)->[b]->[a] -- extend
ext f ys = map f $ inits ys -- Data.List.inits is not lazy

unfoldr f x = map fst bs where
  bs = concat $ takeWhile (/=[]) $ map f as
  as = ext g bs
  g [] = x
  g bs = snd $ last bs

main = print $ unfoldr (\xs -> if null xs then [] else [splitAt 2 xs]) [1..9]

Если пользоваться Data.List.inits, виснет.

(всякие last и вообще inits - не за эффективностью гоняюсь, а за пониманием extend ли это)

Upd: видимо баг. У меня 7.0.3, пора обновлять.

Comments

[nponeccop.livejournal.com]

что значит "не ленивый"? Поясните, что вы хотите сделать. takeWhile (/=[]) и if null xs then [] else не выглядят здоровыми идеями. И что это за extend такой?

Prelude> :m +Data.List
Prelude Data.List> let ext f = map f . inits
Prelude Data.List> take 5 $ ext sum [1..]
[0,1,3,6,10]

ЧЯДНТ?

Оно же scanl:

Prelude> take 5 $ scanl (+) 0 [1..]
[0,1,3,6,10]

[sassa-nf.livejournal.com]

Это ещё не демонстрирует того, что нужно. В этом примере можно "потянуть" лишнее значение и ничего не случится.

Если дело не в ленивости, то почему мой пример виснет (точнее, валится с <<loop>>), если я пользуюсь Data.List.inits, а не определяю свой. Я так понимаю, что inits "тянет" из ys лишнее значение, которого не может быть.


(У меня вообще-то через foldr аккуратненький вариант есть:

unfoldr f x = ys where
  (ys, ts) = unzip $ concat $ foldr (g . f) [] (x:ts)
  g y r = if null y then []
          else y:r

я просто изучаю, как unfoldr и extend связаны)

[nponeccop.livejournal.com]

Непонятно, кто кого тянет. Вот здесь видно, что ничего лишнего не тянется.

Prelude Data.List> let ext = \f -> map f . inits
Prelude Data.List> take 5 $ ext sum [1,2,3,4,5,undefined]
[0,1,3,6,10]
Prelude Data.List> let bot = bot in bot
Interrupted.
Prelude Data.List> let bot = bot
Prelude Data.List> bot
Interrupted.
Prelude Data.List> take 5 $ ext sum [1,2,3,4,5,bot]
[0,1,3,6,10]

[sassa-nf.livejournal.com]

Хм. А почему тогда в моём примере не работает? Разница же только в том, как список раскладывается в Data.List.inits vs мой inits.

[nponeccop.livejournal.com]

Видимо баг был. В 7.4.2 такое работает

import Data.List hiding (unfoldr)
{-
inits xs = [] : inits' xs where
  inits' xs = case xs of
                [] -> []
                x: xs' -> [x]: (map (x :) $ inits' xs')
-}
ext :: ([b]->a)->[b]->[a] -- extend
ext f ys = map f $ inits ys -- Data.List.inits is not lazy

unfoldr f x = map fst bs where
  bs = concat $ takeWhile (/=[]) $ map f as
  as = ext g bs
  g [] = x
  g bs = snd $ last bs

main = print $ unfoldr (\xs -> if null xs then [] else [splitAt 2 xs]) [1..9]

[sassa-nf.livejournal.com]

Прекрасно. А то у меня уже мозги поплыли. :)

[sassa-nf.livejournal.com]

да, а что нужно. Нужно аналог unfoldr написать. Да, там Maybe(a,b) используется, я его через список делаю, потому что изначально показалось, что сплющивать придётся.

[nponeccop.livejournal.com]

Что такое extend? Из комонады? Вот правильная ссылка

И чем вас такой unfoldr не устраивает (с [] вместо Nothing)?

unfoldr f x = case f x of 
	[(a, b)] -> a : unfoldr f b
	[] -> []

И ещё - если кажется, что сплющивать придётся, вам надо на list monad смотреть, может это ближе будет, чем unfoldr/extend.

Вот ещё няшный комонадический unfoldW

import Data.List

extend f ys = map f $ inits ys
unfoldW wf w = fst (wf w) : unfoldW wf (extend (snd . wf) w)

main = take 5 $ unfoldW (\x -> (sum x, 5)) [1..2]

[sassa-nf.livejournal.com]

что за extend - неуверенные шажки к проблеме Comonad. Оно-то и не должно получиться, ибо должно быть Comonad ((->) [a]), но не потыкаешься, не поймёшь.

А пример unfoldr классный, конечно. Я на простую рекурсию как-то и не глянул.

[nponeccop.livejournal.com]

Ну тут же корекурсия. Мне наоборот было интересно видеть эмуляцию корекурсии через рекурсивный комбинатор.

[sassa-nf.livejournal.com]

хехе, вот его, комонадический unfold, я и хотел сварганить :)

[nponeccop.livejournal.com]

Видимо, вас base case вывел из колеи. У корекурсии его нет.

[sassa-nf.livejournal.com]

да, в корекурсии всё не так :) учиться надо. Спасибо за комменты и линки.

[sassa-nf.livejournal.com]

"fmap f == extend (f . duplicate)"

хахаха, у меня вчера по этому поводу тоже истерика была - я как раз вариант первой ссылки до того почитал. По типу должна быть extend (f . extract) :) Спасибо, вторая ссылка подтвердила.


А ещё, если extend f ys = map f $ inits ys, то как же выглядит extract? inits же начинается с [], а как из него что-то получить не ясно (например, чтобы extend extract = id). (допустим, extend f = map f . tail . inits - там вроде бы ясно, extract = last)

[nponeccop.livejournal.com]

А там всё просто - список не является комонадой, а непустой список - не то же самое, что обычный.

См. http://stackoverflow.com/a/12537659/805266

As noted in the comments, you cannot have a comonad instance for lists that may be empty since coreturn has to return something.