# 99 questions/Solutions/46

### From HaskellWiki

(cleanup, comment, format) |
|||

(2 intermediate revisions by 2 users not shown) | |||

Line 8: | Line 8: | ||

<haskell> |
<haskell> |
||

− | -- Negate a Boolean argument |
+ | -- NOT negates a single Boolean argument |

not' :: Bool -> Bool |
not' :: Bool -> Bool |
||

not' True = False |
not' True = False |
||

not' False = True |
not' False = True |
||

− | -- True if both a and b are True |
+ | -- Type signature for remaining logic functions |

and',or',nor',nand',xor',impl',equ' :: Bool -> Bool -> Bool |
and',or',nor',nand',xor',impl',equ' :: Bool -> Bool -> Bool |
||

+ | |||

+ | -- AND is True if both a and b are True |
||

and' True True = True |
and' True True = True |
||

and' _ _ = False |
and' _ _ = False |
||

− | -- True if a or b or both are True |
+ | -- OR is True if a or b or both are True |

or' False False = False |
or' False False = False |
||

or' _ _ = True |
or' _ _ = True |
||

− | -- Negation of 'or' |
+ | -- NOR is the negation of 'or' |

nor' a b = not' $ or' a b |
nor' a b = not' $ or' a b |
||

− | -- Negation of 'and' |
+ | -- NAND is the negation of 'and' |

nand' a b = not' $ and' a b |
nand' a b = not' $ and' a b |
||

− | -- True if either a or b is true, but not if both are true |
+ | -- XOR is True if either a or b is True, but not if both are True |

xor' True False = True |
xor' True False = True |
||

xor' False True = True |
xor' False True = True |
||

xor' _ _ = False |
xor' _ _ = False |
||

− | -- True if a implies b, equivalent to (not a) or (b) |
+ | -- IMPL is True if a implies b, equivalent to (not a) or (b) |

impl' a b = (not' a) `or'` b |
impl' a b = (not' a) `or'` b |
||

− | -- True if a and b are equal |
+ | -- EQU is True if a and b are equal |

equ' True True = True |
equ' True True = True |
||

equ' False False = True |
equ' False False = True |
||

Line 42: | Line 44: | ||

</haskell> |
</haskell> |
||

− | The explicit implementation of logic functions above could be shortened using Haskell's builtin equivalents: |
+ | The above implementations build each logic function from scratch; they could be shortened using Haskell's builtin equivalents: |

<haskell> |
<haskell> |
||

Line 49: | Line 51: | ||

nand' a b = not (and' a b) |
nand' a b = not (and' a b) |
||

nor' a b = not (or' a b) |
nor' a b = not (or' a b) |
||

− | xor' a b = and' (or' a b) (nand' a b) |
+ | xor' a b = not (equ' a b) |

impl' a b = or' (not a) b |
impl' a b = or' (not a) b |
||

equ' a b = a == b |
equ' a b = a == b |
||

</haskell> |
</haskell> |
||

− | Some could be reduced even further through [[Pointfree]] style: |
+ | Some could be reduced even further using [[Pointfree]] style: |

<haskell> |
<haskell> |
||

Line 62: | Line 64: | ||

</haskell> |
</haskell> |
||

− | Anyway, the only remaining difficulty is to generate the truth table. This approach accepts a Boolean function <tt>(Bool -> Bool -> Bool)</tt>, then calls that function with all four combinations of two Boolean values: |
+ | The only remaining task is to generate the truth table; most of the complexity here comes from the string conversion and IO. The approach used here accepts a Boolean function <tt>(Bool -> Bool -> Bool)</tt>, then calls that function with all four combinations of two Boolean values, and converts the resulting values into a list of space-separated strings. Finally, the strings are printed out by mapping <hask>putStrLn</hask> across the list of strings: |

<haskell> |
<haskell> |
||

Line 71: | Line 73: | ||

The table function in Lisp supposedly uses Lisp's symbol handling to substitute variables on the fly in the expression. I chose passing a binary function instead because parsing an expression would be more verbose in haskell than it is in Lisp. Template Haskell could also be used :) |
The table function in Lisp supposedly uses Lisp's symbol handling to substitute variables on the fly in the expression. I chose passing a binary function instead because parsing an expression would be more verbose in haskell than it is in Lisp. Template Haskell could also be used :) |
||

+ | |||

+ | The table function can be generalized to work for any given binary function and domain. |
||

+ | <haskell> |
||

+ | table :: (Bool -> Bool -> Bool) -> String |
||

+ | table f = printBinary f [True, False] |
||

+ | |||

+ | printBinary :: (Show a, Show b) => (a -> a -> b) -> [a] -> String |
||

+ | printBinary f domain = concatMap (++ "\n") [printBinaryInstance f x y | x <- domain, y <- domain] |
||

+ | |||

+ | printBinaryInstance :: (Show a, Show b) => (a -> a -> b) -> a -> a -> String |
||

+ | printBinaryInstance f x y = show x ++ " " ++ show y ++ " " ++ show (f x y) |
||

+ | </haskell> |

## Revision as of 13:42, 25 November 2010

(**) Define predicates and/2, or/2, nand/2, nor/2, xor/2, impl/2 and equ/2 (for logical equivalence) which succeed or fail according to the result of their respective operations; e.g. and(A,B) will succeed, if and only if both A and B succeed.

A logical expression in two variables can then be written as in the following example: and(or(A,B),nand(A,B)).

Now, write a predicate table/3 which prints the truth table of a given logical expression in two variables.

The first step in this problem is to define the Boolean predicates:

-- NOT negates a single Boolean argument not' :: Bool -> Bool not' True = False not' False = True -- Type signature for remaining logic functions and',or',nor',nand',xor',impl',equ' :: Bool -> Bool -> Bool -- AND is True if both a and b are True and' True True = True and' _ _ = False -- OR is True if a or b or both are True or' False False = False or' _ _ = True -- NOR is the negation of 'or' nor' a b = not' $ or' a b -- NAND is the negation of 'and' nand' a b = not' $ and' a b -- XOR is True if either a or b is True, but not if both are True xor' True False = True xor' False True = True xor' _ _ = False -- IMPL is True if a implies b, equivalent to (not a) or (b) impl' a b = (not' a) `or'` b -- EQU is True if a and b are equal equ' True True = True equ' False False = True equ' _ _ = False

The above implementations build each logic function from scratch; they could be shortened using Haskell's builtin equivalents:

and' a b = a && b or' a b = a || b nand' a b = not (and' a b) nor' a b = not (or' a b) xor' a b = not (equ' a b) impl' a b = or' (not a) b equ' a b = a == b

Some could be reduced even further using Pointfree style:

and' = (&&) or' = (||) equ' = (==)

`(Bool -> Bool -> Bool)`, then calls that function with all four combinations of two Boolean values, and converts the resulting values into a list of space-separated strings. Finally, the strings are printed out by mapping

table :: (Bool -> Bool -> Bool) -> IO () table f = mapM_ putStrLn [show a ++ " " ++ show b ++ " " ++ show (f a b) | a <- [True, False], b <- [True, False]]

The table function in Lisp supposedly uses Lisp's symbol handling to substitute variables on the fly in the expression. I chose passing a binary function instead because parsing an expression would be more verbose in haskell than it is in Lisp. Template Haskell could also be used :)

The table function can be generalized to work for any given binary function and domain.

table :: (Bool -> Bool -> Bool) -> String table f = printBinary f [True, False] printBinary :: (Show a, Show b) => (a -> a -> b) -> [a] -> String printBinary f domain = concatMap (++ "\n") [printBinaryInstance f x y | x <- domain, y <- domain] printBinaryInstance :: (Show a, Show b) => (a -> a -> b) -> a -> a -> String printBinaryInstance f x y = show x ++ " " ++ show y ++ " " ++ show (f x y)