Рекурсивный вызов внутри карты

Question

Имея следующую функцию:

between :: a -> [a] -> [[a]] 
between i [] = [[i]] 
between i r@(x:xs) = [[i]++r] ++ map f (between i xs) 
        where f = (\n->[x] ++ n) 

И результат between 0 [1,2] существа:

[[0,1,2],[1,0,2],[1,2,0]] 

Как это возможно? Я могу понять первые два случая:

• [0,1,2] из [[0]++[1,2]]
• [1,0,2] потому map f [[0]++[2]] (где х 1)

ли карта рекурсии, а? И сохраняя ссылку на все начальные x, значит, тогда просто все контакты? В моей голове конечный результат будет что-то вроде:

[[0,1,2],[1,0,2],[2,0]] 

PS: С «карта рекурсии», а что-то долго линии:

\n -> [1] + n 
    \n ->[2] + n 
     \n ->[3] + n 
     \n ->[m] + n 

Answer 1

Прежде всего, давайте исправим эту функцию, чтобы использовать против (:), а не ++, так как первый более эффективен и идиоматичен при добавлении элемента в начало списка, а также может упростить функцию справедливой суммы:

between i [] = [[i]] 
between i r@(x:xs) = (i : r) : map (x:) (between i xs) 

Это будет легче использовать, чтобы пройти через этапы:

between 0 [1, 2] = 
    (0 : [1, 2]) : map (1:) (between 0 [2]) 
    [0, 1, 2] : map (1:) ((0 : [2]) : map (2:) (between 0 [])) 
    [0, 1, 2] : map (1:) ([0, 2] : map (2:) [[0]]) 
    [0, 1, 2] : map (1:) ([0, 2] : [[2, 0]]) 
    [0, 1, 2] : map (1:) [[0, 2], [2, 0]] 
    [0, 1, 2] : [1:[0, 2], 1:[2, 0]] 
    [0, 1, 2] : [[1, 0, 2], [1, 2, 0]] 
    [[0, 1, 2], [1, 0, 2], [1, 2, 0]] 

Итак, эквациональное рассуждение, мы можем выработать шаги GHC взяли прибыть в этом ответе.

Answer 2

Но помните, что между возвращает результат для весь хвост

between 0 [2] 

дает

[[0, 2], [2, 0]] 

применения f добавлять в начало 1 ко всему

[[1, 0, 2], [1, 2, 0]] 

Наконец, мы добавим [[i]++r] (что было бы лучше записать в виде [i:r])

[[0, 1, 2], [1, 0, 2], [1, 2, 0]]