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: Beginners Code - Comments on Style (Brent Yorgey)
2. Re: type vs data, again... (Rustom Mody)
3. Re: type vs data, again... (Gabriel Gonzalez)
----------------------------------------------------------------------
Message: 1
Date: Thu, 21 Mar 2013 11:09:34 -0400
From: Brent Yorgey <[email protected]>
Subject: Re: [Haskell-beginners] Beginners Code - Comments on Style
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
On Sat, Mar 16, 2013 at 11:25:18AM +0100, Heinrich Ody wrote:
> Hi,
>
> I'm trying to learn Haskell by writing a library for automata functions. So
> far I finished some functions that I use to calculate the union and
> intersection of 2 automata for the case of finite words.
>
> I wonder if somebody is willing to give comments on the code? For example
> how I could write a function to be nicer, better to understand etc.
> Please note that I don't know monads yet.
>
> Thanks for your time! Below is my code (I left out some functions to make
> it shorter)
> Greetings,
> Heinrich
>
> ------------------ Code
> import Text.Show.Functions
> import qualified Data.List as List
> import Data.Maybe
> import Prelude hiding (init)
>
> -- b is the type for the alphabet.
> -- Meaning of the parameters are (States, Alphabet, InitStates,
> Trans.Function, FinalStates)
> data NFA l = NFA [State] [l] [State] [(State, l, State)] [State]
You store a list of tuples [(State, l, State)] for the transition map
and then convert it to a function with setTransition. Why not just
store a function of type State -> l -> [State] in the first place
instead of a list of tuples? Actually, l -> State -> [State] would
probably be even more useful. Then to get a function of type l ->
[State] -> [State] you can use 'concatMap'.
However, you can end up with duplicate States this way. So in fact I
would actually recommend using (Set State) in place of [State] (Set is
from Data.Set).
> data State = I Integer
> | S [State]
> deriving Eq
Hmm, I don't understand what the S constructor is for. Why can a
State be a list of States? Hmm, I see from below that this is to
support the 'stateTimes' operation. In that case I think it would be
better to have something like
newtype State a = S a
and then
stateTimes :: [State a] -> [State b] -> [State (a,b)]
which makes State less complicated, and has the added benefit that the
type of stateTimes is more informative. This also means you will have
to make the state type a parameter of NFA, i.e.
data NFA l s = NFA [State s] ...
but that seems nice to me too. All your algorithms should only depend
on e.g. an Eq or Ord constraint on s.
> -- naivly test whether a given word is accepted
> -- for this we forward propagate the current state sets on our input word
> -- we assume the automaton is complete
> isAccepted :: Eq l => NFA l -> [l] -> Maybe Bool
> isAccepted (NFA states alphabet init delta final) word
> = if (List.nub word) `subset` alphabet
> then let f xs sigma = setTransition delta xs sigma
> in Just (((/= []) . (List.intersect final) . (List.foldl f
> init)) word)
> else Nothing
Use foldl' instead of foldl. Also, the uses of List.nub and
List.intersect strongly suggest that you really should be using
Data.Set instead of lists.
-Brent
>
> -- makes an automaton complete s.t. for each pair in (States x Alphabet) a
> the transition function returns a state.
> -- For this a sink state is added to States which is the result of all
> previously unassigned pairs in (States x Alphabet).
> -- This function keeps DFA deterministc. It adds the sinkstate, but it will
> be unreachable.
> makeComplete :: Eq l => NFA l -> NFA l
> makeComplete (NFA states alphabet init delta final) =
> NFA (e:states) alphabet init (unassigned `List.union` delta) final
> where
> -- e is a new state, whose integer value does not occur in
> states
> e = I ((minState states) -1)
> r = ([e] `List.union` states) `times` alphabet
> unassigned = [(s,l,e) | (s,l) <- r, (s,l) `List.notElem` (map
> proj3' delta)]
Given my proposed changes above, the type of makeComplete should
probably be something like
makeComplete :: Eq l => NFA l s -> NFA l (Maybe s)
i.e. you can use Nothing to indicate the new "sink" state.
-Brent
------------------------------
Message: 2
Date: Fri, 22 Mar 2013 09:01:47 +0530
From: Rustom Mody <[email protected]>
Subject: Re: [Haskell-beginners] type vs data, again...
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Message-ID:
<caj+teod1iin8egawtmsp9bbakmjdkcf0d88crof9tp+1mav...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
On Sun, Mar 17, 2013 at 8:55 PM, David McBride <[email protected]> wrote:
> If you hover over "type Object = HashMap Text Value" in
> Data.Aeson.Types in hackage, you will see that the HashMap link links
> to
> http://hackage.haskell.org/packages/archive/unordered-containers/0.2.3.0/doc/html/Data-HashMap-Strict.html#t:HashMap
> ,
> which tells you what package it came from and what to import.
>
Is there some hackage 'hover-click' help/tut somewhere?
Maybe 10 years of python habits... I find hackage often hard to navigate
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20130322/df25c8c9/attachment-0001.htm>
------------------------------
Message: 3
Date: Thu, 21 Mar 2013 20:40:29 -0700
From: Gabriel Gonzalez <[email protected]>
Subject: Re: [Haskell-beginners] type vs data, again...
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"; Format="flowed"
On 03/21/2013 08:31 PM, Rustom Mody wrote:
>
>
> On Sun, Mar 17, 2013 at 8:55 PM, David McBride <[email protected]
> <mailto:[email protected]>> wrote:
>
> If you hover over "type Object = HashMap Text Value" in
> Data.Aeson.Types in hackage, you will see that the HashMap link links
> to
>
> http://hackage.haskell.org/packages/archive/unordered-containers/0.2.3.0/doc/html/Data-HashMap-Strict.html#t:HashMap,
> which tells you what package it came from and what to import.
>
>
> Is there some hackage 'hover-click' help/tut somewhere?
> Maybe 10 years of python habits... I find hackage often hard to navigate
>
All Hackage links point to the module that the function or type came
from, even if it is from a different package. You can use this to find
out which package something comes from. This can be useful if you need
to import a type which is not from the same package as the one you are
currently browsing. You just click the link and see which package it
takes you to.
There are two ways to tell which package you are currently browsing:
* Fastest way: Just look at the url. The part after the "/archive/" is
the package name.
* Most user-friendly way: Click the 'Contents' link in the
upper-right-hand corner. That takes you to the home page of the package
you are currently browsing, which will display all the metadata about
that page.
>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20130321/de13d241/attachment-0001.htm>
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 57, Issue 31
*****************************************
