Таблицы правды из анонимных функций в Haskell - PullRequest
Новая
       61

Таблицы правды из анонимных функций в Haskell

7 голосов
/ 12 декабря 2011

Я пытаюсь сгенерировать таблицу истинности для данного логического выражения. Я мог бы сделать это с помощью создания нового типа данных 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

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

Ответы [ 3 ]

13 голосов
/ 12 декабря 2011

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

{-# 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)
4 голосов
/ 12 декабря 2011

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

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 -> ?))), который ... упс.

Это, конечно, "бесконечный тип".

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

2 голосов
/ 12 декабря 2011

То, что вы просите, вовсе не тривиально.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.

...