StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Standard library functions, reuse of code. Also, your parentheses usage and spacing are really whacked.</p> <pre><code>evaluate (V a) l = case lookup a l of Just x -> x Nothing -> error $ "Unbound variable: " ++ show a -- same as evaluate (V a) l = maybe (error $ "Unbound variable: " ++ show a) id $ lookup a l evaluate (Negation a) l = not $ evaluate a l evaluate (Implication a b) l = evaluate (Negation a `Disjunction` b) l </code></pre> <p>Now, you want a <code>generateTruthTable</code>? That's easy, just take all the possible states of the boolean variables, and tack the evaluated expression on to the end of each.</p> <pre><code>generateTruthTable :: [Variable] -> LogicExpr -> [[(Variable, Bool)]] generateTruthTable vs e = [l ++ [('E', evaluate e l)] | l <- allPossible vs] </code></pre> <p>If only you had a function to generate all those possible states.</p> <pre><code>allPossible :: [Variable] -> [[(Variable, Bool)]] </code></pre> <p>Following my functional gut instinct, this feels like it should be a catamorphism. After all, it does need to look at everything in the list, but return something of a different structure, and it can probably be broken down in a simple way because this is an intro-level CS class. (I don't care what the course number is, this is introductory stuff.)</p> <pre><code>allPossible = foldr step initial where step v ls = ???; initial = ??? </code></pre> <p>Now, <code>foldr :: (a -> b -> b) -> b -> [a] -> b</code>, so the first two parameters must be <code>step :: a -> b -> b</code> and <code>initial :: b</code>. Now, <code>allPossible :: [Variable] -> [[(Variable, Bool)]] = foldr step initial :: [a] -> b</code>. Hmm, this must mean that <code>a = Variable</code> and <code>b = [[(Variable, Bool)]]</code>. What does this mean for <code>step</code> and <code>initial</code>?</p> <pre><code> step :: Variable -> [[(Variable, Bool)]] -> [[(Variable, Bool)]] initial :: [[(Variable, Bool)]] </code></pre> <p>Interesting. Somehow, there needs to be a way to <code>step</code> from a list of variable states and add a single variable to it, and some <code>initial</code> list with no variables at all.</p> <p>If your mind has managed to "click" into the functional programming paradigm already, this should be more than sufficient. If not, you're pretty much screwed in a couple of hours when the assignment is due, regardless of what instruction you've received here. Good luck, and if you're still stuck after the assignment is due, you should ask your professor, or ask a non-urgent question here.</p> <hr> <p>If you're having basic usability issues with the language ("what is the syntax", "what are the run-time semantics", "is there pre-existing functionality for <em>xxx</em>", etc.):</p> <ul> <li><a href="http://www.haskell.org/onlinereport/" rel="nofollow noreferrer">Haskell 98 Language and Libraries</a> is a freely-available, canonical definition of the base language and libraries. More links are available on the <a href="http://www.haskell.org/haskellwiki/Language_and_library_specification" rel="nofollow noreferrer">Haskell wiki</a>.</li> <li>For post-98 language extensions, see the <a href="http://www.haskell.org/ghc/docs/latest/html/users_guide/ghc-language-features.html" rel="nofollow noreferrer">GHC documentation</a>.</li> <li>GHC, Hugs, and other modern Haskell implementations also provide a much richer standard library than is specified in Haskell 98. Full documentation for the <a href="http://www.haskell.org/ghc/docs/latest/html/libraries/" rel="nofollow noreferrer">hierarchical libraries</a> is also available online.</li> <li><a href="http://www.haskell.org/hoogle/" rel="nofollow noreferrer">Hoogλe</a> is a specialized search engine for the extended Haskell standard libraries. <a href="http://holumbus.fh-wedel.de/hayoo/hayoo.html" rel="nofollow noreferrer">Hayoo!</a> is similar but also covers <a href="http://hackage.haskell.org/" rel="nofollow noreferrer">HackageDB</a>, a collection of Haskell libraries far beyond the standard distribution.</li> </ul> <p>I hope your class has provided similar resources, but if not, all of the above are easily discoverable from a Google search.</p> <p>Given proper references, any programmer worth his or her own <a href="http://idioms.thefreedictionary.com/worth+salt" rel="nofollow noreferrer">salt</a> should be able to pick up the syntax of any new language within a few hours, and have a working understanding of the runtime within days. Of course, mastering a new paradigm may take ages, and it's somewhat unfair to hold students to the same standards, but that's what the class is for.</p> <p>Questions about higher-level problems on Stack Overflow may invite less answers, but they'll also be provided with far less petulance :) Homework questions are categorized as "do my work for me!" in most peoples' eyes.</p> <hr> <h2>Spoiler</h2> <p>Please don't cheat. However, just to give you a taste of how awesome stuff can be done in Haskell...</p> <pre><code>{-# LANGUAGE FlexibleInstances, UndecidableInstances #-} {-# LANGUAGE OverlappingInstances, PatternGuards #-} module Expr (Ring(..), (=:>), Expr(..), vars, eval, evalAll) where import Control.Monad.Error infixl 5 =:>, :=> infixl 6 +:, -:, :+, :- infixl 7 *:, :* class (Eq a) => Ring a where (+:) :: a -> a -> a; (-:) :: a -> a -> a; x -: y = x +: invert y (*:) :: a -> a -> a; invert :: a -> a; invert x = zero -: x zero :: a; one :: a (=:>) :: (Ring a) => a -> a -> a (=:>) = flip (-:) instance (Num a) => Ring a where (+:) = (+); (-:) = (-); (*:) = (*) invert = negate; zero = 0; one = 1 instance Ring Bool where (+:) = (||); (*:) = (&&) invert = not; zero = False; one = True data Expr a b = Expr a b :+ Expr a b | Expr a b :- Expr a b | Expr a b :* Expr a b | Expr a b :=> Expr a b | Invert (Expr a b) | Var a | Const b paren :: ShowS -> ShowS paren ss s = '(' : ss (')' : s) instance (Show a, Show b) => Show (Expr a b) where showsPrec _ (Const c) = ('@':) . showsPrec 9 c showsPrec _ (Var v) = ('$':) . showsPrec 9 v showsPrec _ (Invert e) = ('!':) . showsPrec 9 e showsPrec n e@(a:=>b) | n > 5 = paren $ showsPrec 0 e | otherwise = showsPrec 7 a . ('=':) . ('>':) . showsPrec 5 b showsPrec n e@(a:*b) | n > 7 = paren $ showsPrec 0 e | otherwise = showsPrec 7 a . ('*':) . showsPrec 7 b showsPrec n e | n > 6 = paren $ showsPrec 0 e showsPrec _ (a:+b) = showsPrec 6 a . ('+':) . showsPrec 6 b showsPrec _ (a:-b) = showsPrec 6 a . ('-':) . showsPrec 6 b vars :: (Eq a) => Expr a b -> [a] vars (a:+b) = vars a ++ vars b vars (a:-b) = vars a ++ vars b vars (a:*b) = vars a ++ vars b vars (a:=>b) = vars a ++ vars b vars (Invert e) = vars e; vars (Var v) = [v]; vars _ = [] eval :: (Eq a, Show a, Ring b, Monad m) => [(a, b)] -> Expr a b -> m b eval m (a:+b) = return (+:) `ap` eval m a `ap` eval m b eval m (a:-b) = return (-:) `ap` eval m a `ap` eval m b eval m (a:*b) = return (*:) `ap` eval m a `ap` eval m b eval m (a:=>b) = return (=:>) `ap` eval m a `ap` eval m b eval m (Invert e) = return invert `ap` eval m e eval m (Var v) | Just c <- lookup v m = return c | otherwise = fail $ "Unbound variable: " ++ show v eval _ (Const c) = return c namedProduct :: [(a, [b])] -> [[(a, b)]] namedProduct = foldr (\(v, cs) l -> concatMap (\c -> map ((v, c):) l) cs) [[]] evalAll :: (Eq a, Show a, Ring b) => [b] -> a -> Expr a b -> [[(a, b)]] evalAll range name e = [ vs ++ [(name, either error id $ eval vs e)] | vs <- namedProduct $ zip (vars e) (repeat range) ] </code></pre> <pre> $ ghci GHCi, version 6.10.2: http://www.haskell.org/ghc/ :? for help Loading package ghc-prim ... linking ... done. Loading package integer ... linking ... done. Loading package base ... linking ... done. Prelude> :l Expr.hs [1 of 1] Compiling Expr ( Expr.hs, interpreted ) Ok, modules loaded: Expr. *Expr> mapM_ print . evalAll [1..3] 'C' $ Var 'A' :* Var 'B' Loading package mtl-1.1.0.2 ... linking ... done. [('A',1),('B',1),('C',1)] [('A',1),('B',2),('C',2)] [('A',1),('B',3),('C',3)] [('A',2),('B',1),('C',2)] [('A',2),('B',2),('C',4)] [('A',2),('B',3),('C',6)] [('A',3),('B',1),('C',3)] [('A',3),('B',2),('C',6)] [('A',3),('B',3),('C',9)] *Expr> let expr = Var 'A' :=> (Var 'B' :+ Var 'C') :* Var 'D' *Expr> expr $'A'=>($'B'+$'C')*$'D' *Expr> mapM_ print $ evalAll [True, False] 'E' expr [('A',True),('B',True),('C',True),('D',True),('E',True)] [('A',True),('B',True),('C',True),('D',False),('E',False)] [('A',True),('B',True),('C',False),('D',True),('E',True)] [('A',True),('B',True),('C',False),('D',False),('E',False)] [('A',True),('B',False),('C',True),('D',True),('E',True)] [('A',True),('B',False),('C',True),('D',False),('E',False)] [('A',True),('B',False),('C',False),('D',True),('E',False)] [('A',True),('B',False),('C',False),('D',False),('E',False)] [('A',False),('B',True),('C',True),('D',True),('E',True)] [('A',False),('B',True),('C',True),('D',False),('E',True)] [('A',False),('B',True),('C',False),('D',True),('E',True)] [('A',False),('B',True),('C',False),('D',False),('E',True)] [('A',False),('B',False),('C',True),('D',True),('E',True)] [('A',False),('B',False),('C',True),('D',False),('E',True)] [('A',False),('B',False),('C',False),('D',True),('E',True)] [('A',False),('B',False),('C',False),('D',False),('E',True)] </pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload