Написание рекурсивной функции в списках в Haskell

Question

У меня следующий вопрос:

Определите функции

and, or :: [Bool] -> Bool

, которые дают соединение и дизъюнкцию списка логических значений.Например,

and [False, True] = False
or  [False, True] = True

В пустом списке and дает True, а or дает False;объясните причину такого выбора.

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

Мое решение было следующее (но я думаю, что это может быть более эффективным):

and, or :: [Bool] -> Bool

and []             = True
and [True, True]   = True
and [False, False] = True
and [True, False]  = False

or []             = False
or [True, True]   = False
or [False, False] = False
or [True, False]  = True

Answer 1

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

and [] = True
and (True : xs) = ...
and (False : xs) = ...

OK, для пустого списка and - True.Если список начинается с заголовка "True", как вы определяете "истинность" полного списка?Вам нужен рекурсивный вызов или нет?Что если у вас голова "False"?

Случай or аналогичен, просто начните с or [] = False

Обратите внимание, что когда вы начинаете с этих определений, которые уже соответствуют шаблону значений истинности, вам даже не нужноиспользовать && или ||.

Answer 2

Ключевой шаг, который вам нужно сделать, - это думать индуктивно . Ваше текущее решение:

and :: [Bool] -> Bool

and []             = True
and [True, True]   = True
and [False, False] = True
and [True, False]  = False

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

В Haskell вы обычно можете писать свои функции, разбирая тип данных. В этом случае списки. Списки определены как:

data [a] = []
         | a : [a]

Итак, списки имеют два случая: либо пустой список, либо один элемент с хвостом. Давайте начнем писать вашу функцию and, чтобы она соответствовала этим двум случаям для списков:

and []     = True
and (a:as) = ...

Итак, «базовый случай», пустой список, равен True. Но что нам делать в случае списка с одним элементом и некоторым хвостом?

Ну, у нас уже есть функция && в Haskell:

> True && True
True
> True && False
False
> False && True
False
> False && False
False

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

Таким образом, мы можем сделать индуктивным шагом и использовать определяемую нами функцию and вместе с двоичным оператором &&, чтобы завершить наше определение:

and []     = True
and (a:as) = a && (and as)

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

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

Answer 3

Вот несколько битов от меня:

and [] = True
and (True : xs) = and xs
and (False : xs) = False

or [] = False
or (True : xs) = True
or (False : xs) = or xs

Извините, если я испортил режим "домашней работы" этого вопроса.

Answer 4

Я пытался решить эту проблему с помощью сгибов

and = foldl (&&) True
or = foldl (||) False

это было бы простым решением для написания, но я думаю, что оно более абстрактное и занимает [Bool] и && s первый элемент этого списка саккумулятор True этот результат будет следующим аккумулятором к foldl с.

вашим ε / 2