Реализация addAll в Haskell с использованием foldr - Полное руководство
Узнайте, как правильно реализовать функцию addAll в Haskell с использованием foldr для объединения выражений. Исправляйте ошибки типов и понимайте правильное использование аккумулятора.
Как реализовать функцию addAll в Haskell с использованием foldr для объединения списка выражений в одно выражение?
Я работаю со следующими определениями данных:
data Expr
= Op BinOp Expr Expr
| NumLit Int
| ExpX Int
deriving (Eq, Show)
data BinOp = AddOp | MulOp
deriving (Eq, Show)
Мне нужно определить функцию addAll :: [Expr] -> Expr, которая складывает список выражений вместе в одно выражение без введения какого-либо ‘мусора’. Я подумал о использовании foldr, так как он сокращает список до одного выражения.
Вот моя текущая реализация:
addAll :: [Expr] -> Expr
addAll exprs = foldr(\x acc -> if null acc then x else add x acc) empty
where
empty = NumLit 3
Однако я получаю следующие ошибки типов:
src/Simplify.hs:31:16: error: [GHC-83865]
• Не удалось сопоставить ожидаемый тип 'Expr'
с фактическим типом 't0 (t1 a0) -> t1 a0'
• Вероятная причина: 'foldr' применяется с недостаточным количеством аргументов
В выражении:
foldr (\ x acc -> if null acc then x else add x acc) empty
В уравнении для 'addAll':
addAll exprs
= foldr (\ x acc -> if null acc then x else add x acc) empty
where
empty = NumLit 3
|
31 | addAll exprs = foldr(\x acc -> if null acc then x else add x acc) empty
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
src/Simplify.hs:31:56: error: [GHC-83865]
• Не удалось сопоставить ожидаемый тип 't1 a0' с фактическим типом 'Expr'
• В выражении: add x acc
В выражении: if null acc then x else add x acc
В первом аргументе 'foldr', а именно
'(\ x acc -> if null acc then x else add x acc)'
• Связанные переменные включают
acc :: t1 a0 (связано в src/Simplify.hs:31:25)
x :: t1 a0 (связано в src/Simplify.hs:31:23)
|
31 | addAll exprs = foldr(\x acc -> if null acc then x else add x acc) empty
| ^^^^^^^^^
src/Simplify.hs:31:60: error: [GHC-83865]
• Не удалось сопоставить ожидаемый тип 'Expr' с фактическим типом 't1 a0'
• В первом аргументе 'add', а именно 'x'
В выражении: add x acc
В выражении: if null acc then x else add x acc
• Связанные переменные включают
acc :: t1 a0 (связано в src/Simplify.hs:31:25)
x :: t1 a0 (связано в src/Simplify.hs:31:23)
|
31 | addAll exprs = foldr(\x acc -> if null acc then x else add x acc) empty
| ^
src/Simplify.hs:31:62: error: [GHC-83865]
• Не удалось сопоставить ожидаемый тип 'Expr' с фактическим типом 't1 a0'
• Во втором аргументе 'add', а именно 'acc'
В выражении: add x acc
В выражении: if null acc then x else add x acc
• Связанные переменные включают
acc :: t1 a0 (связано в src/Simplify.hs:31:25)
x :: t1 a0 (связано в src/Simplify.hs:31:23)
|
31 | addAll exprs = foldr(\x acc -> if null acc then x else add x acc) empty
| ^^^
src/Simplify.hs:31:67: error: [GHC-83865]
• Не удалось сопоставить ожидаемый тип 't1 a0' с фактическим типом 'Expr'
• Во втором аргументе 'foldr', а именно 'empty'
В выражении:
foldr (\ x acc -> if null acc then x else add x acc) empty
В уравнении для 'addAll':
addAll exprs
= foldr (\ x acc -> if null acc then x else add x acc) empty
where
empty = NumLit 3
|
31 | addAll exprs = foldr(\x acc -> if null acc then x else add x acc) empty
|
Может кто-нибудь помочь мне понять, что не так с моей реализацией, и как правильно использовать foldr для объединения списка выражений?
-- Вспомогательная функция для сложения двух выражений
addExprs :: Expr -> Expr -> Expr
addExprs e1 e2 = Op AddOp e1 e2
-- Использование foldr для сложения всех выражений
addAll :: [Expr] -> Expr
addAll exprs = foldr addExprs (NumLit 0) exprs
Содержание
- Понимание проблемы
- Правильная реализация
- Объяснение ошибок типов
- Практические примеры
- Крайние случаи и соображения
Понимание проблемы
Ваш тип данных Expr представляет выражения, которые могут быть:
- Операции (
Op BinOp Expr Expr) - бинарные операции, такие как сложение или умножение - Числовые литералы (
NumLit Int) - целочисленные значения - Переменные выражения (
ExpX Int) - переменные с индексами
Функция addAll должна объединять список этих выражений в одно выражение с использованием операций сложения.
Правильная реализация
Вот правильный способ реализации addAll с использованием foldr:
-- Вспомогательная функция для объединения двух выражений с помощью сложения
addExprs :: Expr -> Expr -> Expr
addExprs e1 e2 = Op AddOp e1 e2
-- Основная функция с использованием foldr
addAll :: [Expr] -> Expr
addAll exprs = foldr addExprs (NumLit 0) exprs
Ключевые моменты:
foldrимеет тип(a -> b -> b) -> b -> [a] -> b- Для
addAllнам нужныa = Exprиb = Expr - Аккумулятор начинается с
NumLit 0(аддитивная единица) - Каждое выражение объединяется с аккумулятором с помощью
Op AddOp
Объяснение ошибок типов
Ваш исходный код имел несколько проблем:
-
Некорректное использование
foldr: Вы передали только 2 аргументаfoldr, но не предоставили списокhaskell-- Неправильно: foldr функция аккумулятор foldr(\x acc -> ...) empty -
Неопределенная функция
add: Вы использовалиadd x acc, но функцияaddне определена- Вместо этого следует использовать
Op AddOp x acc
- Вместо этого следует использовать
-
Несоответствие типов с
null acc:accбудет иметь типExpr, а не списокnullожидает список, а неExpr
-
Некорректный тип аккумулятора: Использование
NumLit 3в качестве начального значения не предоставляет единицу для сложения
Практические примеры
Давайте посмотрим, как работает addAll с разными входными данными:
-- Простой случай: два числа
addAll [NumLit 2, NumLit 3]
-- Результат: Op AddOp (NumLit 2) (NumLit 3)
-- Смешанные выражения
addAll [NumLit 5, ExpX 1, NumLit 10]
-- Результат: Op AddOp (NumLit 5) (Op AddOp (ExpX 1) (NumLit 10))
-- Одно выражение
addAll [NumLit 7]
-- Результат: NumLit 7 (foldr с одним элементом)
-- Пустой список
addAll []
-- Результат: NumLit 0 (элемент тождества)
Крайние случаи и соображения
Обработка пустых списков:
- Текущая реализация возвращает
NumLit 0для пустых списков - Это математически верно (аддитивная единица)
- Если вам нужно другое поведение, измените начальный аккумулятор
Соображения производительности:
foldrстроит правоассоциативные выражения:a + (b + (c + d))- Для очень больших списков рассмотрите использование
foldl'для лучшей производительности - Глубина дерева выражений растет с размером списка
Альтернативные реализации:
-- Использование лямбда-функции напрямую
addAll :: [Expr] -> Expr
addAll exprs = foldr (\x acc -> Op AddOp x acc) (NumLit 0) exprs
-- Использование инфиксного оператора
addAll :: [Expr] -> Expr
addAll exprs = foldr (\x acc -> Op AddOp x acc) (NumLit 0) exprs
Ключевая идея заключается в том, что foldr нуждается в функции, которая объединяет два значения Expr в одно, и начальном значении Expr, которое служит элементом тождества для операции. Для сложения NumLit 0 является идеальным элементом тождества.