Таблицы истинности из анонимных функций в Haskell

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

> tTable (\x y -> not (x || y))
output:
F F | T
F T | F
T F | F
T T | F

Мой подход:

tbl p = [(uncurry p) tuple | tuple <- allval]
        where allval=[(x,y) | x <- [False,True], y <- [False,True]]

Это работает, но только для 2 аргументов. Я хочу сделать это для любого количества аргументов. Поэтому я решил создать функцию, которая берет аргументы из списка:

argsFromList f []     = f
argsFromList f (x:xs) = argsFromList (f x) xs

Это не работает:

 Occurs check: cannot construct the infinite type: t = t1 -> t
   Expected type: t -> [t1] -> t1 -> t
   Inferred type: (t1 -> t) -> [t1] -> t1 -> t
 In the expression: argsFromList (f x) xs

Я не понимаю, в чем здесь проблема. Я был бы очень признателен, если бы кто-нибудь мог указать мне правильное направление или опубликовать ссылку, которая делает.


boolean logic haskell truthtable
person Moriz Büsing    schedule 12.12.2011    source источник
comment
возможный дубликат Почему такое определение функции не разрешено в хаскелл?   -  person Daniel Wagner    schedule 12.12.2011
comment
Обратите внимание, что вы можете определить лямбду как (\[x,y] -> not (x || y)), что автоматически даст вам поведение функции с произвольным количеством аргументов одного типа.   -  person leftaroundabout    schedule 13.12.2011

Ответы (3)


arrow_upward
4
arrow_downward

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

argsFromList f []     = f
argsFromList f (x:xs) = argsFromList (f x) xs

Попробуем определить тип сами. Сразу видно, что первый аргумент f должен быть функцией хотя бы одного аргумента, второй аргумент (x:xs) — это список, а элементы списка должны быть того же типа, что и первый аргумент f. В первом случае возвращается аргумент f, поэтому окончательный тип возвращаемого значения должен быть таким же, как и первый аргумент. Итак, мы начинаем с этого:

argsFromList :: (a -> ?) -> [a] -> (a -> ?)

Чтобы найти неизвестный тип ?, мы можем посмотреть на второй случай, который состоит из рекурсивного вызова. Аргумент xs имеет тот же тип списка, а аргумент (f x) имеет тип ?. Поскольку он используется в качестве первого аргумента в рекурсивном вызове, который имеет тип (a -> ?), теперь мы можем заключить, что ? имеет тот же тип, что и (a -> ?), который, следовательно, является тем же типом, что и (a -> (a -> ?)), который, следовательно, того же типа, что и (a -> (a -> (a -> ?))), который является... ой.

Конечно, это был бы «бесконечный тип».

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

person C. A. McCann    schedule 12.12.2011
comment
Спасибо! Я позволю этому быть и тогда перейду к новому типу данных. - person Moriz Büsing; 12.12.2011

arrow_upward
13
arrow_downward

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

{-# LANGUAGE FlexibleInstances #-}

class TruthTable a where
  truthTable :: a -> [([Bool], Bool)]

instance TruthTable Bool where
  truthTable b = [([], b)]

instance TruthTable a => TruthTable (Bool -> a) where
  truthTable f = [ (True  : inps, out) | (inps, out) <- truthTable (f True)] ++ 
                 [ (False : inps, out) | (inps, out) <- truthTable (f False)]

Например:

*Main> mapM_ print $ truthTable (&&)
([True,True],True)
([True,False],False)
([False,True],False)
([False,False],False)
person Sjoerd Visscher    schedule 12.12.2011

arrow_upward
2
arrow_downward

То, о чем вы просите, вовсе не тривиально. Haskell не позволяет легко работать с функциями, которые применяют функции с переменным числом аргументов. Например, функции zip из Data.List представлены отдельными вариантами для разного количества аргументов (zip, zip3, zip4, ...). Аналогично, в Control.Monad есть liftM, liftM2, liftM3, ...

По сути, наиболее общий тип, который вы можете присвоить функции с неизвестным количеством аргументов, — это a -> b; одноместная функция истинности — это Bool -> Bool (a = Bool, b = Bool), двуместная функция истинности — это Bool -> (Bool -> Bool) (a = Bool, b = Bool -> Bool), трехместная — это Bool -> (Bool -> (Bool -> Bool)) (a = Bool, b = Bool -> (Bool -> Bool)) , и так далее. Но нет простого способа посмотреть на функцию, в которую вы были переданы, чтобы узнать, какой тип справа от начальной стрелки.

Один тип решения, которое можно заставить работать, включает использование классов типов для определения отдельных экземпляров функции создания таблицы истинности для каждого типа функции-аргумента. Ответ Sjoerd Visscher в этом потоке делает это для всех размеров функций, используя определение рекурсивного экземпляра (обратите внимание на рекурсивное объявление TruthTable a => TruthTable (Bool -> a)). Могут быть и другие решения, которые можно построить с использованием класса типа Applicative.

person Luis Casillas    schedule 12.12.2011