Добавление 2 Int Lists Together F #

Question

Я работаю над домашней работой, и проблема в том, где мы получаем 2 списка int одного размера, а затем добавляем числа вместе. Пример следующим образом.

vecadd [1;2;3] [4;5;6];; would return [5;7;9] 

Я новичок в этом, и мне нужно, чтобы мой код был довольно простым, чтобы я мог учиться на нем. У меня это до сих пор. (Не работает)

let rec vecadd L K = 
     if L <> [] then vecadd ((L.Head+K.Head)::L) K else [];; 

Я по существу хочу просто заменить первый список (L) добавленными номерами. Кроме того, я попытался кодировать его по-другому, используя случаи совпадения.

let rec vecadd L K = 
     match L with 
     |[]->[] 
     |h::[]-> L 
     |h::t -> vecadd ((h+K.Head)::[]) K 

Ни один из них не работает, и я был бы признателен за любую помощь, которую я могу получить.

Answer 1

Первый, ваше представление об изменении первого списка вместо того, чтобы возвращать новый, ошибочно. Мутация (т. Е. Изменение данных на месте) является основной причиной ошибок сегодня (используется как goto, но это уже давно запрещено). Сделать каждую операцию новой базой данных, а не модифицировать существующие, намного безопаснее. И в некоторых случаях это может быть еще более результативным, совершенно контринтуитивно (см. Ниже).

Second, как вы пытаетесь это сделать, вы не делаете то, что, по вашему мнению, делаете. Двойная двоеточие не означает «изменить первый элемент». Это означает «прикрепить элемент вперед».Например:

let a = [1; 2; 3] 
let b = 4 :: a // b = [4; 1; 2; 3] 
let c = 5 :: b // c = [5; 4; 1; 2; 3] 

Вот как списки на самом деле построены: вы начинаете с пустым списком и предметами вставляться в него. Синтаксис [1; 2; 3], который вы используете, - это просто синтаксический сахар для этого. То есть, [1; 2; 3] === 1::2::3::[].

Итак, как мне изменить список, спросите вы? Ответ в том, что нет! Списки F # являются неизменяемыми структурами данных. Создав список, вы больше не сможете его модифицировать.

Эта непреложность позволяет провести интересную оптимизацию. Взгляните еще раз на приведенный выше пример, один с тремя списками a, b и c. Сколько клеток памяти вы считаете этими тремя списками? Первый список состоит из 3-х предметов, второго - 4 и третьего - 5, поэтому общий объем памяти должен быть равен 12, верно? Неправильно! Общий объем памяти, занимаемой этими тремя списками, действителен всего 5 ячеек. Это связано с тем, что список b не является блоком памяти длины 4, а просто номером 4 в паре с указателем на список a. Число 4 называется «голова» списка, а указатель называется «хвостом». Аналогично, список c состоит из одного номера 5 (его «голова») и указателя на список b, который является его «хвостом».

Если списки не были неизменными, их не удалось организовать так: что, если кто-то изменяет мой хвост? Списки должны быть скопированы каждый раз (google «защитная копия»).

Таким образом, единственный способ сделать список - это вернуть новый. То, что вы пытаетесь сделать, может быть описано примерно так: если входные списки пустые, результатом будет пустой список; в противном случае результатом будет сумма хвостов, добавленных с суммой головок. Вы можете записать это в F # почти дословно:

let rec add a b = 
    match a, b with 
    | [], [] -> [] // sum of two empty list is an empty list 
    | a::atail, b::btail -> (a + b) :: (add atail btail) // sum of non-empty lists is sum of their tails prepended with sum of their heads 

Обратите внимание, что эта программа является неполной: она не определяет, какой результат должен быть, когда один вход пуст, а другой нет. Компилятор генерирует предупреждение об этом. Я оставлю решение в качестве упражнения для читателя.

Answer 2

Вы можете перечислить оба списка вместе с List.map2 (см. the docs) Он проходит по обоим спискам попарно, и вы можете дать ему функцию (первый параметр List.map2), применяемую к каждой паре элементов из списки. И это порождает новый список.

let a = [1;2;3] 
let b = [4;5;6] 

let vecadd = List.map2 (+) 

let result = vecadd a b 
printfn "%A" result 

И если вы не хотите больше работать «самим», что-то вроде этого?

let a = [1;2;3] 
let b = [4;5;6] 

let vecadd l1 l2 = 
    let rec step l1 l2 acc = 
     match l1, l2 with 
      | [], [] -> acc 
      | [], _ | _, [] -> failwithf "one list is bigger than the other" 
      | h1 :: t1, h2 :: t2 -> step t1 t2 (List.append acc [(h1 + h2)]) 
    step l1 l2 [] 
let result = vecadd a b 
printfn "%A" result 

Эта функция является рекурсивной функцией, которая принимает два списка и аккумулятор для переноса результата.

• В последнем заявлении матча он делает три вещи
  • Sum глава обоих списков
  • Добавить результат в аккумуляторе
  • Рекурсивный называть себя с новым аккумулятором и хвосты списки
• Первое совпадение возвращает аккумулятор, когда остальные списки пустые
• Второй ответ возвращает ошибку, когда один из списков длиннее другого. Аккумулятор возвращается в результате, когда остальные списки пустые.

Звонок step l1 l2 [] выдает его с помощью двух прилагаемых списков и пустого аккумулятора.