Пытаетесь разобраться (x: xs) и списки?

Question

Меня всегда интересовало, как работают списки, и я запутался в концепции всего (x: xs). Кажется, я просто не обхожу это вокруг головы.

Пример

select :: Ord a => a -> [a] -> [a]
select y [] = []
select y (x:xs)
    | x < y     = x : select y xs
    | otherwise = select y xs

P.S. Я точно знаю, что делает эта функция, но сможет ли кто-нибудь объяснить этот процесс (включая особенно странные знаки Ord a и =>)?

Любые эффективные стратегии будут высоко оценены.

Спасибо заранее. Ян.

Answer 1

Хорошо. Давайте пройдемся по различным синтаксическим элементам здесь.

Строка 1

select :: Ord a => a -> [a] -> [a]

Это объявление типа. Это объявление функции (так как она имеет -> типов).

Функция имеет два аргумента.

• Первое - это одиночное значение любого типа, обозначаемое a (нижний регистр означает, что это полиморфный тип).
• Второй аргумент - это список любого типа, который совпадает с первым аргументом.

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

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

Строка 2

Теперь мы смотрим на строку 2:

select y [] = []

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

если первым аргументом является какое-либо значение (которое мы назовем y), а вторым аргументом является пустой список (обозначаемый шаблоном []), то select оценивается как пустой список.

Строка 3

Строка 3 содержит другой регистр для списков:

select y (x:xs)

Опять же, это часть определения функции select, для случая, когда вторым аргументом является , а не пустой список. Если это не пустой список, то это список с заголовком x и хвостом xs. Конструктор "cons" (:) объединяет начало и конец списка. Это также, как мы сопоставляем образец по списку, чтобы извлечь голову и хвост.

Путем сопоставления с образцом в начале и в конце списка, с помощью (x:xs) мы привязываем новую переменную x к значению заголовка списка и xs к значению хвоста список.

Строки 4 и 5

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

| x < y     = x : select y xs
| otherwise = select y xs

Первый охранник срабатывает, когда x меньше первого аргумента y. Если это так, мы возвращаем новый список с x в заголовке и select, примененным снова к хвосту.

Если это не так, то мы удаляем x из списка и возвращаем только то, что происходит, когда tail вызывается рекурсивно.

---

Для получения дополнительной информации о том, как работает Haskell, я рекомендую вводные тексты, такие как:

• Учим тебя Хаскелю за великое благо.
• Программирование на Haskell.
• Ремесло функционального программирования.

это будет стоить вашего времени.

Answer 2

Мой Haskell в лучшем случае ограничен, но я дам ответ, который могу, если никто другой не сделает ...

select :: Ord a => a -> [a] -> [a]

Это говорит:

ВыборФункция использует любой тип «a», так что этот тип относится к классу типов «Ord» (Orderable).Он принимает один экземпляр типа плюс список типа и возвращает список типа.

Если это помогает, в Java это может быть представлено как (kindof):

<T implements Comparable> List<T> select(T value, List<T> listOfValues);

Фактическое определение функции говорит:

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

Правка: Заказв вышеприведенном контексте означает «вы можете сравнить значения этого типа друг с другом, чтобы определить, что будет« первым »».Т.е. операторы <, = и> определены для значений типа.«Ord» - это TypeClass, определенный (по сути) стандартной библиотекой Haskell (Prelude? Я забыл, как он называется)

Answer 3

(x:xs) - для сопоставления с образцом в ячейке.Когда вы говорите [1,2,3], на самом деле это синтаксический сахар для 1:(2:(3:[])).Таким образом, когда select 1 [1,2,3] вызывается:

select y []     = ... -- pattern skipped; [1,2,3] does not match []
select y (x:xs) = ... -- pattern used, with y = 1, x = 1, and xs = [2,3]

Таким образом, в (x:xs), x является первым элементом списка, а xs является оставшимися элементами.Этот шаблон будет соответствовать только в том случае, если список не пуст.

Что касается синтаксиса Ord a =>, это означает, что «если a является экземпляром класса типа Ord».Int будет работать здесь, потому что у него есть экземпляр для Ord, который может выглядеть следующим образом:

instance Ord Int where
    (<=) = primitiveIntLessThanOrEqual

Если вы оставили Ord a и просто сказали select :: a -> [a] -> [a], тогда x < yне будет работать, потому что это требует аргументов типа в классе Ord:

(<) :: (Ord a) => a -> a -> Bool