Выполнение конкатенации списка реализовано в виде левого сгиба - PullRequest
Новая
       11

Выполнение конкатенации списка реализовано в виде левого сгиба

0 голосов
/ 14 мая 2018

Рассмотрим конкатенацию списка, реализованную в виде сгиба влево, то есть foldl (++) [].Какова сложность этой реализации в ленивом языке, таком как Haskell?Я понимаю, что на строгом языке производительность является квадратичной по общему количеству элементов, но что происходит, когда речь идет о лени?

Я пытался вручную оценить выражение ([1,2,3] ++ [4,5,6]) ++ [7,8,9] (что соответствует foldl (++) [] [[1,2,3], [4,5,6], [7,8,9]]) и кажется, что мы проходим только один раз по каждому элементу, но я не уверен, верны ли мои рассуждения: 

([1,2,3] ++ [4,5,6]) ++ [7,8,9]
= { rewrite expression in prefix notation }
(++) ((++) [1,2,3] [4,5,6]) [7,8,9]
= { the first (++) operation needs to pattern match on its first argument; so it evaluates the first argument, which pattern matches on [1,2,3] }
(++) (case [1,2,3] of {[] -> [4,5,6]; x:xs' -> x:(++) xs' [4,5,6]}) [7,8,9]
= { x = 1, xs' = [2,3] }
(++) (1:(++) [2,3] [4,5,6]) [7,8,9]
= { the first (++) operation can now pattern match on its first argument }
1:([2,3] ++ [4,5,6]) ++ [7,8,9]

Я предположил следующую реализацию (++): 

(++) :: [a] -> [a] -> [a]
xs ++ ys = case xs of [] -> ys
                      (x:xs') -> x : (xs' ++ ys)

1 Ответ

0 голосов
/ 14 мая 2018

Допустим, у нас есть ([1,2,3]++[4,5,6])++[7,8,9]

([1,2,3]++[4,5,6])++[7,8,9]
(1:([2,3]++[4,5,6))++[7,8,9]
1:(([2,3]++[4,5,6])++[7,8,9])
1:((2:([3]++[4,5,6])++[7,8,9])
1:2:(([3]++[4,5,6])++[7,8,9])
1:2:(3:([]++[4,5,6])++[7,8,9])
1:2:3:(([]++[4,5,6])++[7,8,9])
1:2:3:([4,5,6]++[7,8,9])
1:2:3:4:([5,6] ++ [7,8,9])
1:2:3:4:5:([6] ++ [7,8,9])
1:2:3:4:5:6:([] ++ [7,8,9])
1:2:3:4:5:6:[7,8,9]
[1,2,3,4,5,6,7,8,9]

Обратите внимание, как каждый элемент в первом списке нужно было перемещать дважды?Это потому, что было два с конца.В общем, если у нас есть (((a1++a2)++a3)++..an) каждый элемент в списке, то ai нужно будет перемещать n-i раз.

Итак, если вы хотите, чтобы весь список был квадратичным.Если вам нужен первый элемент, и у вас есть списки n, это операции n-1* (нам нужно выполнить пошаговый случай ++ n раз).Если вам нужен i-й элемент, это число операций для всех элементов перед ним, плюс k-1, где он был в k-м списке, считая с конца.

*Плюс операции n от самого foldl, если мы хотим быть педантичными

...