Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: using record in aeson (David McBride)
2. Re: How would you improve this program? (Lorenzo Bolla)
3. Data structure for Propositional Logic formulas
(Alexander Raasch)
4. first open source haskell project and a mystery to boot (Alia)
5. Re: Data structure for Propositional Logic formulas
(Daniel Schoepe)
6. Re: Data structure for Propositional Logic formulas
(Benedict Eastaugh)
----------------------------------------------------------------------
Message: 1
Date: Wed, 12 Oct 2011 11:21:03 -0400
From: David McBride <[email protected]>
Subject: Re: [Haskell-beginners] using record in aeson
To: Rick Murphy <[email protected]>
Cc: [email protected]
Message-ID:
<can+tr429fqfblzybg4hujz8pfadqjnbpff1ycd6drbppcz7...@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
The problem is that in parseObject, from the moment you type 'return',
you are then in pure code. But you are trying to do applicative
functions as if you are still in the Parser monad. Here is a way to
rewrite this.
First rewrite
data MyRecord = MyRecord {s :: T.Text, u :: T.Text} deriving (Show)
because we are using Text not String, then
parseObject o' = mapM toMyPair (M.assocs o')
where
toMyPair :: (T.Text, Value) -> J.Parser MyPair
toMyPair (t, Object o'') = do
rec <- MyRecord <$> (o'' .: "type") <*> (o'' .: "value") ::
J.Parser MyRecord
return $ R (t, rec)
toMyPair _ = error "unexpected"
That is, stay in the parser monad and pull out the things you need
using do notation, then return the whole thing back into the parser
monad. You could have also gone:
toMyPair (t, Object o'') = do
typ <- o'' .: "type"
val <- o'' .: "value"
return $ R (t, MyRecord typ val)
On Tue, Oct 11, 2011 at 9:17 PM, Rick Murphy <[email protected]> wrote:
> Hi All:
>
> I've been elaborating on aeson examples and wondered whether someone
> could clarify the syntax for using a record in a pair. My goal is to
> substitute a record for the list of pairs created through the data
> constructor O [(T.Text, Value)] in MyPair below. Reason being to embed
> the semantics of the json file into the record. To reproduce, just
> uncomment the lines in the source below.
>
> The json file structure is as follows:
> {"outer":{"type":"literal","value":"rick"}}
>
> Note my naive attempt in the commented lines returns the following
> message from ghci. 'f0 b0' doesn't give me much to go on.
>
> -- E1.hs:35:41:
> -- ? ? Couldn't match expected type `MyRecord' with actual type `f0 b0'
> -- ? ? In the expression: MyRecord <$> o'' .: "type" <*> o'' .: "value"
> -- ? ? In the first argument of `R', namely
> -- ? ? ? `(t, MyRecord <$> o'' .: "type" <*> o'' .: "value")'
> -- ? ? In the expression: R (t, MyRecord <$> o'' .: "type" <*> o'' .:
> "value")
> -- Failed, modules loaded: none.
>
> {-# LANGUAGE OverloadedStrings #-}
>
> module Main where
>
> import Control.Applicative
> import Control.Monad (mzero)
>
> import qualified Data.ByteString as B
> import qualified Data.Map as M
> import qualified Data.Text as T
>
> import Data.Aeson
> import qualified Data.Aeson.Types as J
> import Data.Attoparsec
>
> -- data MyRecord = MyRecord {s :: String, u :: String} deriving (Show)
>
> data MyPair = O (T.Text, [(T.Text, Value)])
> ? ? ? ? ? -- | R (T.Text, MyRecord)
> ? ? ? ? ? ? ?deriving (Show)
>
> data ExifObject = ExifObject [MyPair]
> ? ? ? ? ? ? ? ?deriving Show
>
> data Exif ? ? ? = Exif [ExifObject]
> ? ? ? ? ? ? ? ?deriving Show
>
> instance FromJSON ExifObject
> ?where
> ? ?parseJSON (Object o) = ExifObject <$> parseObject o
> ? ? ?where
> ? ? ? ?parseObject o' = return $ map toMyPair (M.assocs o')
>
> ? ? ? ?toMyPair (t, Object o'')= O (t, M.assocs o'')
> -- ? ? ?toMyPair (t, Object o'')= R (t, MyRecord <$> o'' .: "type" <*>
> o'' .: "value")
> ? ? ? ?toMyPair _ ? ? ? ? ? ? ?= error "unexpected"
>
> ? ?parseJSON _ ? ? ? ? ?= mzero
>
> parseAll :: B.ByteString -> [ExifObject]
> parseAll s = case (parse (fromJSON <$> json) s) of
> ?Done _ (Error err) ?-> error err
> ?Done ss (Success e) -> e:(parseAll ss)
> ?_ ? ? ? ? ? ? ? ? ? -> []
>
> main :: IO ()
> main = do s <- B.readFile "e1.json"
> ? ? ? ? ?let p = Exif $ parseAll s
> ? ? ? ? ?print p
>
> --
> Rick
>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
------------------------------
Message: 2
Date: Wed, 12 Oct 2011 16:25:31 +0100
From: Lorenzo Bolla <[email protected]>
Subject: Re: [Haskell-beginners] How would you improve this program?
To: [email protected]
Message-ID:
<cadjgtrwdyvdhhojq0tyyfvj4fqlzsj7yto96k+dqr25lgea...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
On Tue, Oct 11, 2011 at 4:28 PM, Brent Yorgey <[email protected]>wrote:
> On Tue, Oct 11, 2011 at 02:04:23PM +0300, Ovidiu Deac wrote:
>
> > join "\n" result -- from Data.List.Utils
>
> By the way, 'join "\n" result' is better written 'unlines result' (and
> 'join' is better written 'intercalate'). (Otherwise I completely agree
> with your email.)
>
>
Fixed.
https://github.com/lbolla/stanford-cs240h/blob/master/lab1/lab1.hs
Thanks for the suggestions.
L.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20111012/0a724bf6/attachment-0001.htm>
------------------------------
Message: 3
Date: Wed, 12 Oct 2011 17:38:51 +0200
From: Alexander Raasch <[email protected]>
Subject: [Haskell-beginners] Data structure for Propositional Logic
formulas
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Hi,
I wrote this program to work with formulas in propositional logic:
data Formula =
| Variable Char
| Not Formula | And Formula Formula | Or Formula Formula
| Imply Formula Formula | Equivalent Formula Formula
deriving (Eq)
instance Show Formula where
show (Variable v) = [v]
show (Not f) = "~" ++ show f
show (And f g) = "(" ++ show f ++ " & " ++ show g ++ ")"
show (Or f g) = "(" ++ show f ++ " v " ++ show g ++ ")"
show (Imply f g ) = "(" ++ show f ++ " -> " ++ show g ++ ")"
show (Equivalent f g ) = "(" ++ show f ++ " <-> " ++ show g ++ ")"
To make a formula you can do something like:
ghci> let f = Or (Variable 'C') (And (Variable 'A') (Not (Variable 'C')))
ghci> f
(C v (A & ~C))
So, my questions are:
1. Do you think this is an elegant solution or would you define custom
operators (or, and, ->, <->) instead? Or something completely different?
2. If I pack this code into a module how would add a new logic
connective like xor or nand to Formula? Meaning, can I add another type
constructor to it?
3. Is there a way to "nest" data definitions, e.g. I would like to
replace the 'Variable Char' type constructor by 'Literal Char', whereas
a Literal is either a Variable or a negated Variable. Literals can be
negated, too.
Thanks a lot.
Alex
------------------------------
Message: 4
Date: Wed, 12 Oct 2011 11:59:30 -0700 (PDT)
From: Alia <[email protected]>
Subject: [Haskell-beginners] first open source haskell project and a
mystery to boot
To: "[email protected]" <[email protected]>
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=iso-8859-1
Hi folks,
Given that I received such excellent help from this newsgroup recently, I
wanted to share my first
open-source haskell project available here:
https://github.com/aliakhouri/newsagent
It's a simple command line feed (atom, rss) retriever and analyzer in the early
stages of development,
using the excellent feed / tagsoup libs to download and analyze feeds from the
net.
The real intention is to use it as a platform to learn about information
retrieval and machine learning
techniques in haskell.
To this end, I was searching for classification algorithms and I was on the
lookout for a nice
clear implementation in haskell of canonical decision tree based classification
algorithms.
My first discovery was an old DecisionTree package on hackage but it's poorly
documented
and has no examples of usage. So I kept searching...
Then I found an hpaste page (http://hpaste.org/steps/11355) which looked at lot
more
promising, but it also has no example or documentation. In fact, it's an island
of code without
any references (I don't know who the author is) and nobody has ever referred to
it by url or by
blog post). It's a mystery to me.
In any case, I've tried to create a working example but I'm stuck because you
can't mix
strings and numbers in a list, and I can't decide whether that's when the
author gave up,
or whether I've missed the point. Like I said it's a mystery.
I would appreciate if anyone could shed some light on this whimsical problem.
In case you are wondering why this is relevant to the beginner's forum. Well...
firstly, I am a beginner, and, er... the code is short enough to serve
pedagogical purposes? (-;
AK
<ID3.hs>
-- | This module is a generic implementation
--?? of the ID3 decision tree algorithm.
--
-- A choice node on a ``continuous'' attribute is
-- handled by splitting the population in two via the mean attribute value.
module ID3 where
import Data.Ord
import Data.List
import qualified Data.Map as Map
data DecisionTree item outcome = Choice (item -> DecisionTree item outcome)
?????????????????????????????? | Leaf outcome
data Attribute item = Discrete (item -> Integer)
??????????????????? | Continuous (item -> Double)
runDecisionTree :: DecisionTree item outcome -> item -> outcome
runDecisionTree (Leaf outcome) _ = outcome
runDecisionTree (Choice f) item = runDecisionTree (f item) item
id3 :: (Ord outcome) => [Attribute item] -> [(item, outcome)] -> DecisionTree
item outcome
-- When there are no unused attributes left, select the most common outcome.
id3 [] xs = Leaf $ fst $ head $ sortBy (comparing (negate.snd)) $ histogram
(map snd xs)
-- When all the items have the same outcome, pick that outcome
id3 attrs xs | allEqual (map snd xs) = Leaf $ snd $ head xs
-- Otherwise pick the attribute with minimum entropy
???????????? | otherwise =
??? let (bestAttr:moreAttrs) = sortBy (comparing (informationGain xs)) attrs in
??? case bestAttr of
???????? Discrete attr ->
???????????? let attrTreeMap = Map.fromList attrTrees
???????????????? allAttrValues = nub $ map (attr . fst) xs
???????????????? subtree v = id3 moreAttrs (filter (\(x,_) -> v /= attr x) xs)
???????????????? attrTrees = [(v, subtree v) | v <- allAttrValues]
???????????? in Choice $ \item -> case Map.lookup (attr item) attrTreeMap of
?????????????????????????????????????? Just subtree -> subtree
?????????????????????????????????????? Nothing -> error "id3: encountered a
discrete attribute value that wasn't in the training set"
???????? Continuous attr ->
???????????? let meanv = mean (map (attr.fst) xs)
???????????????? ltTree = id3 moreAttrs (filter (\(x,_) -> attr x <? meanv) xs)
???????????????? gtTree = id3 moreAttrs (filter (\(x,_) -> attr x >= meanv) xs)
???????????? in Choice $ \item -> if attr item < meanv
???????????????????????????????????? then ltTree
???????????????????????????????????? else gtTree
informationGain :: Ord outcome => [(item, outcome)] -> Attribute item -> Double
informationGain xs (Discrete attr) =
??? currentEntropy - sum (map term allAttributeValues)
??? where
??? currentEntropy = entropy (map snd xs)
??? term a = probabilityOf (==a) * entropy (outcomesFor (==a))
??? probabilityOf f = fromIntegral (length (outcomesFor f)) / fromIntegral
(length xs)
??? outcomesFor f = map snd $ filter (f . attr . fst) xs
??? allAttributeValues = nub $ map (attr . fst) xs
informationGain xs (Continuous attr) =
??? currentEntropy - term (< meanv) - term (>= meanv)
??? where
??? currentEntropy = entropy (map snd xs)
??? term f = probabilityOf f * entropy (outcomesFor f)
??? probabilityOf f = fromIntegral (length (outcomesFor f)) / fromIntegral
(length xs)
??? outcomesFor f = map snd $ filter (f . attr . fst) xs
??? meanv = mean (map (attr.fst) xs)
entropy :: Ord a => [a] -> Double
entropy xs = sum $ map (\(_,n) -> term (fromIntegral n)) $ histogram xs
??? where term 0 = 0
????????? term n = - (n / num) * log (n / num) / log 2
????????? num = fromIntegral (length xs)
histogram :: Ord a => [a] -> [(a, Int)]
histogram = buildHistogram Map.empty
??? where buildHistogram map [] = Map.assocs map
????????? buildHistogram map (x:xs) = buildHistogram (Map.insertWith (+) x 1
map) xs
-- Simple "utility" functions
allEqual :: Eq a => [a] -> Bool
allEqual = and . mapAdjacent (==)
mapAdjacent :: (a -> a -> b) -> [a] -> [b]
mapAdjacent f xs = zipWith f xs (tail xs)
mean :: (Real a, Fractional n) => [a] -> n
mean xs = realToFrac (sum xs) / realToFrac (length xs)
--------------------------------------------------------------------
-- Testing Area
--------------------------------------------------------------------
outlook s
??? | s == "sunny"??? = 1
??? | s == "overcast" = 2
??? | s == "rain"???? = 3
temp :: (Real a, Fractional n) => a -> n
temp i = (realToFrac i) / (realToFrac 100)
humidity :: (Real a, Fractional n) => a -> n
humidity i = (realToFrac i) / (realToFrac 100)
windy x
??? | x == False = 0
??? | x == True? = 1
-- attributes
a1 = Discrete outlook
a2 = Continuous temp
a3 = Continuous humidity
a4 = Discrete windy
outlookData? =
["sunny","sunny","overcast","rain","rain","rain","overcast","sunny","sunny","rain","sunny","overcast","overcast","rain"]
tempData???? = [85, 80, 83, 70, 68, 65, 64, 72, 69, 75, 75, 72, 81, 71]
humidityData = [85, 90, 78, 96, 80, 70, 65, 95, 70, 80, 70, 90, 75, 80]
windyData??? = [False, True, False, False, False, True, True, False, False,
False, True, True, False, True]
outcomes???? = [0,0,1,1,1,0,1,0,1,1,1,1,1,0]
d1 = zip outlookData outcomes
d2 = zip tempData outcomes
d3 = zip humidityData outcomes
d4 = zip windyData outcomes
t1 = id3 [a1] d1
t2 = id3 [a2] d2
t3 = id3 [a3] d3
t4 = id3 [a4] d4
--t5 = id3 [a1,a2,a3,a4] [d1,d2,d3,d4]
-- doesn't work because you can't mix strings and numbers in a list
--
----------------
</ID3.hs>
------------------------------
Message: 5
Date: Wed, 12 Oct 2011 22:58:47 +0200
From: Daniel Schoepe <[email protected]>
Subject: Re: [Haskell-beginners] Data structure for Propositional
Logic formulas
To: Alexander Raasch <[email protected]>, [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="us-ascii"
On Wed, 12 Oct 2011 17:38:51 +0200, Alexander Raasch <[email protected]> wrote:
> Hi,
>
> I wrote this program to work with formulas in propositional logic:
>
> data Formula =
> | Variable Char
> | Not Formula | And Formula Formula | Or Formula Formula
> | Imply Formula Formula | Equivalent Formula Formula
> deriving (Eq)
It would be better to have Formula only include a few basic primitives
(And, Or and Not is a popular choice), and define the rest in terms of
those. More on that in the answer to your second question.
> instance Show Formula where
> show (Variable v) = [v]
> show (Not f) = "~" ++ show f
> show (And f g) = "(" ++ show f ++ " & " ++ show g ++ ")"
> show (Or f g) = "(" ++ show f ++ " v " ++ show g ++ ")"
> show (Imply f g ) = "(" ++ show f ++ " -> " ++ show g ++ ")"
> show (Equivalent f g ) = "(" ++ show f ++ " <-> " ++ show g ++ ")"
>
> To make a formula you can do something like:
>
> ghci> let f = Or (Variable 'C') (And (Variable 'A') (Not (Variable 'C')))
> ghci> f
> (C v (A & ~C))
>
> So, my questions are:
>
> 1. Do you think this is an elegant solution or would you define custom
> operators (or, and, ->, <->) instead? Or something completely
> different?
You can still define such operators afterwards, and I think it would
make formulas easier to read and write, for example:
(<&&>) :: Formula -> Formula
a <&&> b = And a b
> 2. If I pack this code into a module how would add a new logic
> connective like xor or nand to Formula? Meaning, can I add another type
> constructor to it?
If you chose a set of "primitives" capable of expressing every other
formula, you can define xor, nand, etc. later as normal functions:
nand :: Formula -> Formula -> Formula
nand a b = Not (And a b)
> 3. Is there a way to "nest" data definitions, e.g. I would like to
> replace the 'Variable Char' type constructor by 'Literal Char', whereas
> a Literal is either a Variable or a negated Variable. Literals can be
> negated, too.
The parameters to constructors are not limited to built-in types and the
type you are defining. So for your example, something like this would
work:
data Literal = Variable Char | NegVar Char
data Formula = Literal | And .......
That would of course introduce some redundancy, since `Not (Variable c)'
and `NegVar c' would represent the same formula.
Cheers,
Daniel
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 835 bytes
Desc: not available
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20111012/0ce2251c/attachment-0001.pgp>
------------------------------
Message: 6
Date: Wed, 12 Oct 2011 22:24:04 +0100
From: Benedict Eastaugh <[email protected]>
Subject: Re: [Haskell-beginners] Data structure for Propositional
Logic formulas
To: Alexander Raasch <[email protected]>
Cc: [email protected]
Message-ID:
<caoco6ulcpw7ji74qrcjpxrujeoeggcxhvwxsz8xu_2eapju...@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
Hi Alex,
since Daniel has done a nice job of actually answering your questions,
I shall just note that I have a module similar to this available on
Hackage as part of my hatt package, which generates truth tables for
formulae in classical propositional logic.
http://hackage.haskell.org/package/hatt
http://hackage.haskell.org/packages/archive/hatt/1.3.0/doc/html/Data-Logic-Propositional.html
Benedict
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 40, Issue 16
*****************************************
