Сглаживание списка в Haskell

Question

Я пытаюсь сгладить произвольное количество списков внутри списков в Haskell. Я знаю, что этот вопрос уже был опубликован в Stack, но ответы на них слишком сложны для меня (я новичок в Haskell), или нет ответа, удовлетворяющего мои потребности (например, concat не будет работать для меня, потому что я должен фактически написать эту функцию сглаживания самостоятельно для учебного пособия по экзамену). Я также пишу свою собственную функцию сглаживания в Haskell, чтобы понять, почему в топ-решениях используются модули.

Вот что у меня есть.

flatten :: [[a]] -> [a] 
flatten [] = [] 
flatten (x:xs) = flatten x:flatten xs 

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

Inferred type is not general enough 
*** Expression : flatten 
*** Expected type : [[a]] -> [a] 
*** Inferred type : [[[a]]] -> [[a]] 

EDIT: Извините! Я неправильно понял вопрос об экзамене. Все элементы списка на самом деле должны быть списками. Например, [[[1,2,3], [4,5,6]], [7,8,9]], а не [1, [2,3,4]].

Answer 1

Давайте рассмотрим тип вашей функции: если у вас есть список списков, это написано [[a]]. Вы хотите сгладить это только к списку, [a], поэтому тип сглаживания должен быть [[a]] -> [a]. Вы также можете обмануть и найти тип concat, так как вы знаете, что вы его повторно реализуете.

Теперь рассмотрим реализацию. Первый случай соответствует [] и возвращает []. Соответствует ли это [[a]] -> [a]? Да, поскольку параметр [] является пустым списком типа [something], где что-то может быть типа [a]. Возвращаемое значение также соответствует нашему типу, потому что это пустой список типа [whatever], где все может иметь тип a.

Теперь посмотрим на второй корпус, соответствует ли он типу [[a]] -> [a]? Согласование образцов с (x:xs) означает x имеет тип [a] и xs имеет тип [[a]], это прекрасно. Проблема заключается в ваших рекурсивных вызовах: первый вызывает flatten с x, который имеет тип [a]. Но мы знаем, что параметр flatten должен быть типа [[a]].

Кстати, вы будете чаще получать более четкие или более точные сообщения об ошибках типа, если сначала объявите тип своей функции. Это связано с тем, что компилятор может немедленно остановиться, если обнаружил противоречие с заявленным вами. Если вы исключите подпись, компилятор только проверяет, что определение согласуется с самим собой. Когда я объявляю тип GHC говорит мне:

 
    Couldn't match type `a' with `[a0]' 
     `a' is a rigid type variable bound by 
      the type signature for flatten :: [[a]] -> [a] at x.hs:20:1 
    Expected type: [[a0]] 
     Actual type: [a] 
    In the first argument of `flatten', namely `x' 
    In the first argument of `(:)', namely `flatten x' 

Это именно то, что мы нашли проверки типа сами, вручную. Аргумент, который мы передали flatten, должен иметь тип [[a]], но мы фактически передавали значение типа [a].

Answer 2

Шаг 1: укажите свои данные. Вам нужен тип данных, который поддерживает произвольное вложение. [a] нет, поэтому вы не сможете решить проблему таким образом.

Итак, как будут выглядеть данные? Как насчет некоторых обозначений Лиспа:

a 
() 
(a b c) 
((a b) c d) 
(a (b c) d (e (f))) 

Похоже, что элемент может быть атомом или списком.Так скажем, предыдущее предложение в Haskell:

data Element t = -- "an element is either ..." 
    = Atom t  -- "an atom ..." 
    | List [Element t] -- "or a list of elements" 
    deriving (Show)  -- "and please print things for me too, okay?" 

Шаг 2: обходе данные. Теперь вам нужно написать функцию, которая выравнивает Element t в списке. Как будет выглядеть подпись типа?

Я предлагаю flatten :: Element t -> [t]. Для его реализации, он будет нуждаться в двух случаях - один для Atom с, и один для List с:

flatten :: Element t -> [t] 
flatten (Atom x) = .... 
flatten (List xs) = ..... 

Помните, что каждое уравнение имеет оценить в [t]. Удачи!

Answer 3

[[[1,2,3], [4,5,6]], [7,8,9]] также не является допустимым списком Haskell. Он содержит два элемента; первый - [[1,2,3], [4,5,6]], который является [[Int]], а второй - [7,8,9], который равен [Int].

список в Haskell всегда типа [a] для некоторого a, который должен быть тот же для всех элементов списка. Это означает, что если вы имеете дело с вложенными списками, каждый элемент должен иметь такую ​​же степень вложенности.

Кажется маловероятным, что основной экзамен Haskell попросит вас сгладить произвольные уровни гнездования. Это почти наверняка просто хочет, чтобы вы реализовали flatten :: [[a]] -> [a], который вы можете сказать по типу, только удаляет один «уровень» списка. Вы можете назвать его в списках, таких как [[[1], [[2]], [[3]]], который имеет тип [[[Int]], но тип четко говорит о том, что результат будет [[Int]], то есть он вернет [[1], [2], [3]], а не [1, 2, 3].

Проблема с тем, что вы пытаетесь сделать то, что, когда ваш flatten получает аргумент типа [[a]] и делит его на (x:xs) (если он не был пуст), то x будет элементом этого [[a]] списка, так что будет иметь тип [a]. Затем вы пытаетесь вызвать на нем flatten, чтобы вы могли сгладить «весь путь вниз», но flatten принимает аргумент типа [[a]] и x имеет тип [a].

Другой способ думать о том, почему это не может работать в том, что если он сделал работу, вы в конце концов добраться до последнего «уровня» списка, и x не будет даже тип списка на всех , Но вы затем передадите его на flatten, который попытается сопоставить его с любым из шаблонов [] или (x:xs) и должен потерпеть неудачу. Ошибки типа, которые вы получаете, мешают этому.

Answer 4

Ну, в Haskell все вложенные списки имеют равномерную глубину вложенности для всех элементов. Это является следствием системы типов, которая требует, чтобы все элементы списка были одного типа.

Нечто подобное следующему определению никогда не typecheck:

example = [1, [2, 3, 4], [[5, 6], [7]]] 

Первый элемент 1 :: Integer, второй один [2, 3, 4] :: [Integer], и так далее.

Та же проблема относится к отредактированном Например:

[[[1,2,3], [4,5,6]], [7,8,9]] 

Первый элемент этого списка будет иметь вид, как [[Integer]], в то время как второй будет иметь что-то вроде [Integer]. Но это не допускается.

Второе: это не только то, что списки не могут иметь неравномерную глубину, но также не может существовать функция, которая будет «смотреть» на разные вложенные списки на разных глубинах. Функция такого типа, как [[a]] -> [a], «очистит» один уровень вложения от своего входного списка, но будет обрабатывать a как непрозрачный тип - он не знает, какой тип a есть, поэтому, если вы передадите аргумент [[[Integer]]], flatten не может использовать тот факт, что a - [Integer] за тот один аргумент, который вы ему дали, - a может быть что угодно!

Таким образом, единственное сглаживание списка, которое может быть выполнено в Haskell, - это удаление вложенности на некоторой глубине, фиксированной по типу функции. Так, например, flatten снимает только один уровень вложенности, и с помощью функциональной композиции мы можем отделить два или более: flatten . flatten :: [[[a]]] -> [a], flatten . flatten . flatten :: [[[[a]]]] -> [a] и так далее.

Answer 5

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

{-# LANGUAGE FlexibleInstances 
    , OverlappingInstances 
    , IncoherentInstances #-} 

class Nested a where 
    flatten :: [a] -> [Int] 

instance Nested Int where 
    flatten = id 

instance (Nested a) => Nested [a] where 
    flatten xss = concatMap flatten xss 

-- e.g. now this works ... 
flatten [[1 :: Int,2,3],[2,3,4]] 
-- ... and this too ... 
flatten [[[1 :: Int,2,3],[2,3,4]],[[25]]] 
-- ... but this won't work 
-- flatten [[[1 :: Int,2,3],[2,3,4]],25] 

Если вы хотите разрешить произвольную вложенность , вы должны обернуть типов:

{-# LANGUAGE ExistentialQuantification } 

class Foo a 

instance Foo Int 

instance Foo [a] 

data F = forall a. Foo a => F a 

test = F [F (1 :: Int), F [F (2 :: Int), F [F (3 :: Int), F [F (4 :: Int)]]]] 

Теперь вы можете написать flatten для такого типа.

Однако я бы не рекомендовал исследовать это как новичок. Сначала вам нужно лучше понять, как именно на самом деле должен работы. Этот материал просто не является тривиальным, он идет против зерна системы типа Хаскелла, поэтому каждое объяснение будет смутить вас. Попытайтесь использовать типы так, как они предназначены для использования, и вернитесь к таким вопросам, когда вам действительно нравятся общие случаи использования.