Пояснение о типе метода Concat

Question

Может кто-нибудь объяснить, почему не работает тип списка источников в моей реализации concat?

conc::[[a]]->[a]
conc xs@(x1:xs')=foldr (:) [] xs

Почему список источников должен быть [a], а не [[a]]? Если я хочу конкатить [[1,2],[3,4]], это не тип [[a]], а не [a], а тип элемента - [a].

Я получаю следующую ошибку:

Couldn't match type `a' with `[a]'
      `a' is a rigid type variable bound by
        the type signature for:
          conc :: forall a. [[a]] -> [a]

Answer 1

foldr (:) [] xs == xs - это True для любого xs. Это означает, что foldr (:) [] является функцией идентификации в списках. Этот факт широко известен, он настолько известен в Haskell, что опытный программист на Haskell автоматически читает foldr (:) [] как id.

Один способ увидеть foldr c n состоит в замене «против» (то есть (:)) на c и [] на n в данном списке. Замена (:) на (:) и [] на [], очевидно, ничего не изменит:

[a, b, ..., z]  ==>  a : b : ... : z : []  ==  [a, b, ..., z]

Заменив (:) s на (++), с другой стороны, все списки внутри входного списка будут объединены в один:

[a, b, ..., z]  ==>  a ++ b ++ ... ++ z

чего вы и хотели достичь.

Таким образом, правильная реализация для concat с foldr равна foldr (++) [].

Answer 2

На самом деле компилятор показывает полезную подсказку в ошибке (фактически на пару строк ниже, чем сообщение, которое вы опубликовали)

Expected type: [a]
Actual type: [[a]]

В следующем коде аргумент действительно имеет тип [[a]], но результат также имеет тип [[a]], что противоречит определению типа:

conc :: [[a]] -> [a]
conc xs@(x1:xs') = foldr (:) [] xs

xs в коде имеет тип [[a]], и вы перебираете его с помощью foldr и добавляете каждый элемент, который имеет тип [a], в список. В результате вы получите список типа [[a]].