Как использовать sml, чтобы написать функцию, чтобы превратить список из двух кортежей в плоский список? - PullRequest
Новая
       9

Как использовать sml, чтобы написать функцию, чтобы превратить список из двух кортежей в плоский список?

0 голосов
/ 25 сентября 2019

У меня возникла проблема, из-за которой необходимо преобразовать список кортежей в плоский список, например:

[(1,2), (3,4), (5,6)] можно перевернутьв [1,2,3,4,5,6]

Я пытался написать такую ​​функцию: 

fun helper2(nil,b) = []
|   helper2(a,nil) = []
|   helper2(a::l1,b::l2) =l1::l2

fun flatten2 [] = []
|   flatten2 ((a,b)::tl) = helper2(a,b)

Показывает: 

val flatten2 = fn : ('a list * 'a list list) list -> 'a list list

И когда я попытался запустить его с помощью команды flatten2[(1,2),(3,4),(5,6)]; Это выдаст мне следующее сообщение об ошибке: 

stdIn:1.2-1.29 Error: operator and operand do not agree [overload conflict]
  operator domain: ('Z list * 'Z list list) list
  operand:         ([int ty] * [int ty]) list
  in expression:
    flatten2 ((1,2) :: (3,4) :: (<exp>,<exp>) :: nil)

Мои вопросы:

  1. Почему SML видит a иЗначения b в виде списков, а не просто a и b
  2. Как я могу пересмотреть мой код, чтобы SML мог видеть a и b как 'a и' b not lists
  3. Как заставить этот код работатькак это должно быть?

спасибо

Ответы [ 2 ]

3 голосов
/ 25 сентября 2019

Первый вопрос: почему тип выглядит как ('a list * 'a list list), это потому, что вывод типа просматривает эту часть кода: 

|   helper2(a::l1,b::l2) =l1::l2
                            ^^
                           here

Имейте в виду, что тип "cons"Оператор (::) - 'a -> 'a list -> 'a list, он склеивает отдельный элемент в список элементов того же типа.Таким образом, SML пришел к выводу, что, независимо от того, что l1 и l2, существует связь, что l2 является списком того, что есть l1. 

fun helper2(nil,b) = []

Говорит, что a должен быть спискомпотому что nil имеет тип 'a list.Следовательно, l2 должен быть списком списков (некоторого типа 'a).

Вопрос 2 и 3: Я не совсем уверен, как исправить код, как он написан.Я бы, наверное, написал что-то вроде этого: 

fun helper2 [] accum = List.rev accum
|   helper2 ((a,b)::tl) accum =  helper2 tl (b :: a :: accum);

fun flatten2 list = helper2 list [];

helper2 выполняет всю грязную работу.Если список ввода пуст, то мы все сделали, и мы можем вернуть инвертированный аккумулятор , который мы строили.Во втором случае мы добавляем вещи в аккумулятор.Мы сопоставляем образец по голове и хвосту списка.Это сопоставление с образцом означает, что вход имеет тип ('a * 'a) list (список кортежей, в которых оба элемента имеют одинаковый тип).В голове у нас есть кортеж, и мы называем первый и второй элементы a и b соответственно.Мы добавляем a, затем b в аккумулятор и рекурсивно вызываем helper2 в конце списка.В конце концов, мы пройдемся по всем элементам в списке, а затем останемся только с аккумулятором, который, напомним, содержит все элементы, но в обратном порядке.Вызов List.rev переворачивает аккумулятор, и это наш ответ.

И когда я загружаю и запускаю его, я получаю это: 

- flatten2 [(1,2), (3,4), (5,6)];
val it = [1,2,3,4,5,6] : int list
1 голос
/ 25 сентября 2019

Почему SML видит значения a и b в виде списков, а не просто a и b

Крис уже подробно ответил на это.

Вы проходитеa в качестве первого аргумента для helper2, который ожидает список в качестве первого аргумента.И вы передаете b в качестве второго аргумента helper2, который использует свой второй аргумент, b::l2, также список, в качестве хвоста списка, где a - заголовок.Так что b должен быть списком этих списков.

Это не имеет никакого смысла и, скорее всего, является следствием запутанного синтаксиса: вы передаете то, что думаете об отдельных элементах a иb в flatten2, но когда вы имеете дело с ними в helper2, они теперь списки , где головы называются a и b.Это не одно и то же a и b.

Как мне пересмотреть мой код, чтобы SML мог видеть a и b как 'a и' b, а не списки

Вы можете отказаться от вспомогательной функции, чтобы начать с: 

fun flatten2 []             = []
  | flatten2 ((a,b)::pairs) = a :: b :: flatten2 pairs

Назначение вспомогательной функции состоит в том, чтобы она могла накапливать результат во время рекурсии, потому что эта версия flatten2 использует многопространство стека.Это может быть сделано с дополнительным аргументом, так что flatten2 не нужно упоминать об этом:

Это версия, созданная Крисом.

Как заставить этот код работатькак это должно быть?

Вы можете сделать этот код разными способами.Были упомянуты два способа использования явной рекурсии.

Вот несколько альтернатив, использующих функции высшего порядка: 

(* Equivalent to my first version *)
fun flatten2 pairs =
  foldr (fn ((a,b), acc) => a :: b :: acc) [] pairs

(* Equivalent to Chris'es version *)
fun flatten2 pairs =
  rev (foldl (fn ((a,b), acc) => b :: a :: acc) [] pairs)

(* Yet another alternative *)
fun concatMap f xs =
  List.concat (List.map f xs)

fun flatten2 pairs =
  concatMap (fn (a,b) => [a,b]) pairs
...