Реализация конкатенации вручную в haskell

Question

Как я могу реализовать оператор конкатенации в Haskell вручную? Это то, что я имею до сих пор, но я борюсь с рекурсией в конце:

data MyList a = Empty | Element a (MyList a)
 deriving Show

concatenation:: MyList a -> MyList a -> MyList a
concatenation Empty Empty = Empty
concatenation a Empty = a
concatenation Empty a = a
concatenation x y = ???

Answer 1

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

concatenation:: MyList a -> MyList a -> MyList a
concatenation Empty Empty = -- ...
concatenation Empty (Element b bs) = -- ...
concatenation (Element a as) Empty = -- ...
concatenation (Element a as) (Element b bs) = -- ...

Теперь мы можем стремиться разрешить эти случаи. Объединение двух Empty списков вернет пустой список, поэтому Empty.

concatenation Empty Empty = Empty

Если первый список Empty, а последний - нет, то мы возвращаем второй список.

concatenation Empty (Element b bs) = Element b bs

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

concatenation (Element a as) Empty = Element a as

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

concatenation (Element a as) (Element b bs) = Element a (concatenation as (Element b bs))

это дает нам следующий код:

concatenation:: MyList a -> MyList a -> MyList a
concatenation Empty Empty = Empty
concatenation Empty (Element b bs) = Element b bs
concatenation (Element a as) Empty = Element a as
concatenation (Element a as) (Element b bs) = Element a (concatenation as (Element b bs))

Мы можем сократить реализацию с как шаблоны :

concatenation:: MyList a -> MyList a -> MyList a
concatenation Empty Empty = Empty
concatenation Empty bl@(Element b bs) = bl
concatenation al@(Element a as) Empty = al
concatenation (Element a as) bl@(Element b bs) = Element a (concatenation as bl)

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

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

concatenation Empty Empty = Empty
concatenation Empty (Element b bs) = Element b bs

до:

concatenation Empty bl = bl

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

Можем ли мы сделать то же самое с последними двумя строками?

concatenation (Element a as) Empty = Element a as
concatenation (Element a as) bl@(Element b bs) = Element a (concatenation as bl)

оба имеют в результате конструктор Element и a в качестве первого элемента. Поскольку объединение as и Empty в конечном итоге concatenation as Empty = as, таким образом, мы можем выполнить рекурсивный вызов и в первом случае и использовать:

concatenation (Element a as) bl = Element a (concatenation as bl)

и это приводит к:

concatenation :: MyList a -> MyList a -> MyList a
concatenation Empty bl = bl
concatenation (Element a as) bl = Element a (concatenation as bl)

мы можем опустить второй параметр здесь с помощью:

concatenation :: MyList a -> MyList a -> MyList a
concatenation Empty = id
concatenation (Element a as) = Element a . concatenation as

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

Answer 2

Просто используйте стандартную рекурсию:

concatenation:: MyList a -> MyList a -> MyList a
concatenation Empty l = l
concatenation (Element e l1) l2 = Element e (concatenation l1 l2)

Почему это останавливается? Второе правило состоит в том, чтобы брать каждый элемент первого списка по одному и вкладывать его до объединения Empty и второго списка, то есть самого второго списка (первое правило).

  concatenation Element 1 (... Element n (Empty)) l2
= Element 1 (concatenation Element 2 (... Element n (Empty))) l2 -- second rule
= ...
= Element 1 (Element 2 (... Element n (concatenation Empty l2))) -- second rule
= Element 1 (Element 2 (... Element n (l2))) -- first rule