Сравнение двух списков в SML с использованием Fold/Map?

Question

Скажем, у меня есть два списка, [1,2,3] и [9,2,3]. Скажем, мне дали третье значение, 2. Если я хочу узнать, является ли это значение в обоих списках, но я могу использовать только foldl/foldr/map для этого (без среды или пользовательской рекурсии вне карты/foldr/foldl), как я могу это сделать? Это вопрос домашней работы для класса программирования, и я застрял на нем уже неделю.

Answer 1

Существует ряд вещей, которые вы можете сделать, чтобы приблизиться к этому назначение:

1. Написать заглушку для функции, так что вы знаете, что вы имеете дело с:

   fun isInBoth (xs, ys, z) = ... 
   

   где эта функция возвращает что-то типа bool.

2. Подумайте о том, как вы могли бы решить эту проблему, если бы это было просто членство в один список:

   (* Using built-in functions *) 
   fun isInList (xs, z) = List.exists (fn x => x = z) xs 
   
   (* Using recursion directly *) 
   fun isInList ([], z) = false 
       | isInList (x::xs, z) = x = z orelse isInList (xs, z) 
   

3. исключает использование map, так как это создает «список б, а не bool.

4. Действуйте решить эту проблему с помощью откидного для всего один списка:

   fun isInList (xs, z) = foldl (fn (x, acc) => ...) ... xs 
   

   где acc этого значение, которое foldl накапливается при каждом рекурсивном вызове.

   Первый ... должен отражать делает ли присутствие значения x в списке разницу в результате функции, или если ранее считали элементом сделал разницу (используя acc как прокси).

   Второй ... является BOOL, который представляет значение по умолчанию в случае xs является пустым, и является базовым сценарием для рекурсии этого foldl выполняет.

   Помните, что складывание в стандартном ML - это процесс с нетерпением: он проходит через весь список, за исключением случаев, когда он пришел к выводу, что элемент присутствует. По этой причине в среднем List.exists является лучшим комбинатором для поиска в одном списке. В лениво оцененных языках складывание может быть эквивалентным.

5. Действуйте решить эту проблему для двух списков, тривиальный:

   fun isInBoth (xs, ys, z) = isInList (xs, z) andalso isInList(ys, z) 
   

6. (Необязательно) рассмотрит, как можно переплетать эти два рекурсивных вызовов и создать парное складывание.На самом деле, есть функция называется ListPair.foldl, которая работает следующим образом:

   (* Finds the largest positive integer in two lists, or 0 *) 
   fun max3 (x, y, z) = Int.max (x, Int.max(y, z)) 
   fun maxTwoLists (xs, ys) = ListPair.foldl max3 0 (xs, ys) 
   

   , но он приходит с раздражающим побочным эффектом:

   val huh = maxTwoLists ([1,2,3], [1,2,3,4]) (* gives 3 *) 
   

   Так что, если вы хотите перебрать два списка и рассматривать их элементы попарно , и продолжите поиск в одном списке, если другой конец, и прекратите свертывание, если ваш критерий удовлетворен или больше не может быть удовлетворен, вы имеете дело с схемой рекурсии, которую ни List.foldl, ни ListPair.foldl не поддерживает. Если бы это было не школа упражнения, которые требовали складывания, это было бы одно решение:

   fun isInList (xs, z) = List.exists (fn x => x = z) xs 
   fun isInBoth (x::xs, y::ys, z) = 
       x = z andalso isInList (y::ys, z) orelse (* no needs to look at more xs *) 
       y = z andalso isInList (x::xs, z) orelse (* no needs to look at more ys *) 
       isInBoth (xs, ys, z)      (* keep looking in both *) 
       | isInBoth ([], ys, z) = false    (* not found in xs *) 
       | isInBoth (xs, [], z) = false    (* not found in ys *) 
   

   Абстрагируясь шаблон рекурсии в функции, аналогичной ListPair.foldl, вероятно, не так уж полезно.

Answer 2

Вы можете просто использовать некоторую форму гарантии от функции foldl, в сочетании с and оператором как:

fun intersection l1 l2 v = (#1 (foldl (fn (x,y) => if (x = (#2 y)) then (true, (#2 y)) else y) (false, v) l1)) andalso (#1 (foldl (fn (x,y) => if (x = (#2 y)) then (true, (#2 y)) else y) (false, v) l2)) 

Это элегантное, простое и в одной строке (хотя, возможно, для вы, вероятно, хотите, чтобы это было более чем в одной строке).