Почему этот первый Haskell функционирует СБОЙ для обработки бесконечных списков, в то время как этот второй отрывок УСПЕШНО ВЫПОЛНЯЕТСЯ с бесконечными списками?

Попробуйте развернуть выражение вручную:

 take 5 (myWords_FailsOnInfiniteList  (cycle "why "))
 take 5 (foldr step [] (dropWhile charIsSpace (cycle "why ")))
 take 5 (foldr step [] (dropWhile charIsSpace ("why " ++ cycle "why ")))
 take 5 (foldr step [] ("why " ++ cycle "why "))
 take 5 (step 'w' (foldr step [] ("hy " ++ cycle "why ")))
 take 5 (step 'w' (step 'h' (foldr step [] ("y " ++ cycle "why "))))

Какое следующее расширение? Вы должны увидеть, что для сопоставления с образцом для шага вам необходимо знать, пустой это список или нет. Чтобы это выяснить, нужно хотя бы немного его оценить. Но этот второй член оказывается сокращением foldr самой функцией, для которой вы выполняете сопоставление с образцом. Другими словами, пошаговая функция не может смотреть на свои аргументы, не вызывая себя, и поэтому у вас бесконечная рекурсия.

Сравните это с расширением вашей второй функции:

myWords_anotherReader (cycle "why ")
foldr step [""] (cycle "why ")
foldr step [""] ("why " ++ cycle "why ")
step 'w' (foldr step [""] ("hy " ++ cycle "why ")
let result = foldr step [""] ("hy " ++ cycle "why ") in
    ['w':(head result)] ++ tail result
let result = step 'h' (foldr step [""] ("y " ++ cycle "why ") in
    ['w':(head result)] ++ tail result

Вы, вероятно, видите, что это расширение будет продолжаться, пока не будет достигнуто пространство. Как только пробел будет достигнут, «результат заголовка» получит значение, и вы получите первый элемент ответа.

Я подозреваю, что эта вторая функция переполнится для бесконечных строк, не содержащих пробелов. Вы понимаете, почему?

Вторая версия фактически не оценивает результат до тех пор, пока после не начнет производить часть своего собственного ответа. Первая версия оценивает результат немедленно путем сопоставления с ним.

Ключ к этим бесконечным спискам заключается в том, что вы должны создать что-то , прежде чем вы начнете требовать элементы списка, поэтому что выходные данные всегда могут «опережать» входные.

(мне кажется, что это объяснение не очень ясное, но это лучшее, что я могу сделать)

The library function foldr has this implementation (or similar):

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f k (x:xs) = f x (foldr f k xs)
foldr _ k _ = k

The result of myWords_FailsOnInfiniteList depends on the result of foldr which depends on the result of step which depends on the result of the inner foldr which depends on ... and so on an infinite list, myWords_FailsOnInfiniteList will use up an infinite amount of space and time before producing its first word.

The step function in myWords_anotherReader does not require the result of the inner foldr until after it has produced the first letter of the first word. Unfortunately, as Apocalisp says, it uses O(length of first word) space before it produces the next word, because as the first word is being produced, the tail thunk keeps growing tail ([...] ++ tail ([...] ++ tail (...))).

In contrast, compare to

myWords :: String -> [String]
myWords = myWords' . dropWhile isSpace where
    myWords' [] = []
    myWords' string =
        let (part1, part2) = break isSpace string
        in part1 : myWords part2

using library functions which may be defined as

break :: (a -> Bool) -> [a] -> ([a], [a])
break p = span $ not . p

span :: (a -> Bool) -> [a] -> ([a], [a])
span p xs = (takeWhile p xs, dropWhile p xs)

takeWhile :: (a -> Bool) -> [a] -> [a]
takeWhile p (x:xs) | p x = x : takeWhile p xs
takeWhile _ _ = []

dropWhile :: (a -> Bool) -> [a] -> [a]
dropWhile p (x:xs) | p x = dropWhile p xs
dropWhile _ xs = xs

Notice that producing the intermediate results is never held up by future computation, and only O(1) space is needed as each element of the result is made available for consumption.

Addendum

So, here's the revised code. I usually try to avoid head and tail, merely because they are partial functions, and also because I need practice writing the pattern matching equivalent.

myWords :: String -> [String]
myWords string = foldr step [""] (dropWhile charIsSpace строка)
 где 
шаг пространство соотв | charIsSpace space = "": согласно
 шаг char (x: xs) = (char: x): xs
 step _ [] = ошибка «это должно быть невозможно»

(Aside: You may not care, but the words "" == [] from the library, but your myWords "" = [""]. Similar issue with trailing spaces.)

Looks much-improved over myWords_anotherReader, and is pretty good for a foldr-based solution.

\n -> tail $ myWords $ replicate n 'a' ++ " b"

It's not possible to do better than O(n) time, but both myWords_anotherReader and myWords take O(n) space here. This may be inevitable given the use of foldr.

Worse,

\n -> head $ head $ myWords $ replicate n 'a' ++ " b"

myWords_anotherReader was O(1) but the new myWords is O(n), because pattern matching (x:xs) requires the further result.

You can work around this with

myWords :: String -> [String]
myWords = foldr step [""] . dropWhile isSpace
   where 
      step space acc | isSpace space = "":acc
      step char ~(x:xs)              = (char:x):xs

The ~ introduces an "irrefutable pattern". Irrefutable patterns never fail and do not force immediate evaluation.