Элементы парного обмена в списке с использованием Ocaml

Question

Я начинающий Ocaml, и не могу понять рекурсивность хвоста или перечислить итерацию. Как мы можем перебирать список через 2s и менять пары?

let rec swap = function 
| a :: (b :: _ as t) -> b::a::swap t | smaller -> smaller;; 
let newlist = swap [1;2;3;4];; 
List.iter print_int newlist; 

Например, 1234, функция подкачки замена 1 и 2, а затем главный список все еще на 2, и его замена 2 и 3, тогда как она должна быть на уровне 3 и замену 3 и 4.

Answer 1

То, что вы пытаетесь сделать в swap должны быть

let rec swap = function 
    | a :: b :: tail -> b :: a :: (swap tail) 
    | whatever -> whatever 

Таким образом, нужно поменять местами два элемента на голове и продолжить то, что после них.

Однако есть проблемы. Давайте посмотрим, что происходит, скажем, в случае swap [1; 2; 3; 4; 5; 6] вызова:

1. swap вызывается с [1; 2; 3; 4; 5; 6]
2. a согласованный с 1, b сочетается с 2, и ...

.. ..2.1. swap называется [3; 4; 5; 6]

.... 2.2. внутри этого второго вызова a соответствует 3, b соответствует 4 и ...

........ 2.2.1. swap называется [5; 6]

........ 2.2.2. внутри этого третьего вызова a соответствует 5, b соответствует 6 и ...

............ 2.2.2.1. swap вызывается с [] (пустой список)

............ 2.2.2.2. Этот вызов возвращает обратно пустой список

........ 2.2.3. ... и подобрано в предыдущем swap вызова добавить b и a начала его, производя 6 :: 5 :: [] или [6; 5]

........ 2.2.4. который возвращается

.... 2.3. ... и подобрано в предыдущем swap вызова, чтобы добавить (свой собственный) b и a начала его, производя 4 :: 3 :: [6; 5] или [4; 3; 6; 5]

.... 2.4. который возвращается

3. ...и подобран в предыдущем swap вызова, чтобы добавить (собственный) b и a начала него, производя 2 :: 1 :: [4; 3; 6; 5] или [2; 1; 4; 3; 6; 5]
4. , который возвращается в качестве конечного результата

Обратите внимание, как всю сеть из swap звонков пришлось быть пройдено в обоих направлениях:

вызова 1, swap [1; 2; 3; 4; 5; 6] => вызов 2, swap [3; 4; 5; 6] => называют 3, swap [5; 6] => называют 4, swap [], возвращает [], теперь возвращается => называют 3, возвращается [6; 5] => вызов 2, возвращает [4; 3; 6; 5] => вызов 1, возвращает [2; 1; 4; 3; 6; 5].

Это означает, что все время, когда программа идет «вниз», она должна сохранять предыдущий путь в памяти, чтобы он мог вернуться назад. Если в вашем списке, скажем, два миллиона записей, весь путь будет составлять миллион звонков, и он должен храниться в памяти. Если вы запустите такую ​​вещь, у вас закончится пространство стека.

Как решить эту проблему? Обычная техника - использовать какой-то «аккумулятор».

let rec swap_helper acc = function 
    | a :: b :: tail -> swap_helper (a :: b :: acc) tail 
    | a :: [] -> a :: acc 
    | [] -> acc ;; 

let swap2 lst = List.rev (swap_helper [] lst) 

Что это за функции? Попробуем посмотреть, что произойдет, если мы позвоним swap2 [1; 2; 3; 4; 5; 6]. Он начинается с вызова swap_helper [] [1; 2; 3; 4; 5; 6].

1. a сопоставляется с 1, b сочетается с 2, tail сочетается с [3; 4; 5; 6], поэтому мы называем swap_helper [1; 2] [3; 4; 5; 6]. Но вот и вот! Когда этот следующий вызов возвращается, мы ничего не делаем с результатом, поэтому нет причин возвращаться - компилятор выдает код, чтобы вернуть результат, который мы получим в swap_helper [1; 2] [3; 4; 5; 6] сразу, не возвращаясь к исходному коду - потому что в этом исходном вызове ничего не осталось. Это называется оптимизацией хвостового вызова.

2. Сейчас мы находимся в swap_helper [1; 2] [3; 4; 5; 6] вызова, где a согласован с 3, b согласован с 4 и tail согласован с [5; 6], поэтому мы называем следующий swap_helper [3; 4; 1; 2] [5; 6] и там опять ничего не оставалось делать после этого, поэтому мы не собираюсь возвращаться сюда больше!

3. Итак, swap_helper [3; 4; 1; 2] [5; 6] звонок. Здесь a - 5, b - 6, tail - []. Мы переходим к swap_helper [5; 6; 3; 4; 1; 2] [], и мы находимся здесь , а не, так как вам больше нечего делать!

4. swap_helper [5; 6; 3; 4; 1; 2] [] попадает в последний случай матча и немедленно возвращает [5; 6; 3; 4; 1; 2] - но не каких-либо промежуточных swap_helper вызовов, они уже забыли, нет никакой работы, чтобы сделать в тех, кто остался, - но прямо к первоначальному swap2 звонку!

Сейчас в swap2 мы поменяем список мы получили от swap_helper и получить наш [2; 1; 4; 3; 6; 5], как хотелось бы.

Итак, чтобы повторить: в этом коде, когда swap_helper называет себя, ничего не остается, поэтому нет причин возвращаться, поэтому нет причин тратить память на запоминание «пути назад», поскольку мы не собираемся вернуться назад. В исходном коде мы не могли этого сделать, потому что swap звонил сам себе и все еще должен был склеить a и b на результат этого второго вызова после его готовности.