Send Beginners mailing list submissions to
beginners@haskell.org
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
beginners-requ...@haskell.org
You can reach the person managing the list at
beginners-ow...@haskell.org
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: type of pattern matching (David Virebayre)
2. Re: type of pattern matching (Michael Mossey)
3. Re: type of pattern matching (Brent Yorgey)
4. Re: Dynamic Programming in Haskell (Heinrich Apfelmus)
5. Re: Re: Dynamic Programming in Haskell (Daniel Fischer)
6. Re: what's a proper way to make a Set typeclass? and why is
it not done already? (Markus L?ll)
7. Re: Some beginning questions for Haskell (Magnus Therning)
8. Re: what's a proper way to make a Set typeclass? and why is
it not done already? (Brent Yorgey)
----------------------------------------------------------------------
Message: 1
Date: Wed, 7 Jul 2010 09:27:24 +0200
From: David Virebayre <dav.vire+hask...@gmail.com>
Subject: Re: [Haskell-beginners] type of pattern matching
To: Michael Mossey <m...@alumni.caltech.edu>
Cc: beginners@haskell.org
Message-ID:
<aanlktik5qoofkqetn_7qjl70ials5xinsfk5co7nd...@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
On Wed, Jul 7, 2010 at 9:19 AM, Michael Mossey <m...@alumni.caltech.edu> wrote:
> doSomething :: Maybe Result
> doSomething item = case item of
> Â note@(Note _ _ _ _ _) -> Just $ process note
> Â _ Â Â Â Â Â Â Â Â Â Â -> Â Nothing
>
> But I don't like writing "Note _ _ _ _ _"
>
isNote (Note _ _ _ _ _) = True
isNote _ = False
doSomething :: Maybe Result
doSomething item | isNote item = Just $ process note
| otherwise = Nothing
But I don't like writing "Note _ _ _ _ _"
------------------------------
Message: 2
Date: Wed, 07 Jul 2010 01:15:42 -0700
From: Michael Mossey <m...@alumni.caltech.edu>
Subject: Re: [Haskell-beginners] type of pattern matching
To: David Virebayre <dav.vire+hask...@gmail.com>
Cc: beginners@haskell.org
Message-ID: <4c3437ae.6040...@alumni.caltech.edu>
Content-Type: text/plain; charset=UTF-8; format=flowed
David Virebayre wrote:
> On Wed, Jul 7, 2010 at 9:19 AM, Michael Mossey <m...@alumni.caltech.edu>
> wrote:
>> doSomething :: Maybe Result
>> doSomething item = case item of
>> note@(Note _ _ _ _ _) -> Just $ process note
>> _ -> Nothing
>>
>> But I don't like writing "Note _ _ _ _ _"
>>
>
>
> isNote (Note _ _ _ _ _) = True
> isNote _ = False
>
> doSomething :: Maybe Result
> doSomething item | isNote item = Just $ process note
> | otherwise = Nothing
>
> But I don't like writing "Note _ _ _ _ _"
I think this is pretty good because I can use isNote with a filter in
another function.
Thanks,
Mike
------------------------------
Message: 3
Date: Wed, 7 Jul 2010 10:15:56 +0100
From: Brent Yorgey <byor...@seas.upenn.edu>
Subject: Re: [Haskell-beginners] type of pattern matching
To: beginners@haskell.org
Message-ID: <20100707091556.ga29...@seas.upenn.edu>
Content-Type: text/plain; charset=us-ascii
On Wed, Jul 07, 2010 at 08:26:50AM +0100, Stephen Tetley wrote:
> Hi Michael
>
> Untested - maybe you can use Record puns (section 7.3.15.of the GHC
> manual). Though they might only work if you have used field names in
> your data type.
>
> {} swaps for _ _ _ _ _ _ so it would be:
>
> > doSomething :: Maybe Result
> > doSomething item = case item of
> > note@(Note {}) -> Just $ process note
> > _ -> Nothing
Nope, this works in general, whether you've used field names or not.
I use this trick all the time. Also, I see no reason to use a case;
why not just
doSomething item@(Note{}) = Just $ process item
doSomething _ = Nothing
-Brent
------------------------------
Message: 4
Date: Wed, 07 Jul 2010 11:30:28 +0200
From: Heinrich Apfelmus <apfel...@quantentunnel.de>
Subject: [Haskell-beginners] Re: Dynamic Programming in Haskell
To: beginners@haskell.org
Message-ID: <i11hfk$82...@dough.gmane.org>
Content-Type: text/plain; charset=UTF-8; format=flowed
Ali Razavi wrote:
> In order to practice Haskell, I decided to program some algorithms from the
> CLRS book. Particularly, I tried to implement the Matrix Chain Order from
> Chapter 15 on Dynamic Programming.
> Here is my code. It seems to work, however, it looks ugly and it was a
> nightmare to debug. I appreciate comments about a more elegant solution, and
> generally the best way to implement these kinds of algorithms in Haskell.
> Style improvement suggestions are also welcome.
Dynamic programming algorithms follow a common pattern:
* Find a suitably small collection of subproblems that can be used to
solve the original problem
* Tabulate the solutions to the subproblems, also called *memoization*
These are two separate concerns and, unlike the prototype imperative
solutions, are best implemented separately.
Thanks to lazy evaluation, memoization can be implemented very elegantly
in Haskell. First, it should be a higher-order functions and second, you
don't need to implement a particular order by which the memo table is
filled, lazy evaluation will figure that out for you. You already know
the latter trick, but here is another example:
http://article.gmane.org/gmane.comp.lang.haskell.beginners/554
But it doesn't stop here: there are very systemic ways to tackle the
first part of dynamic programming, i.e. to *derive* dynamic programming
algorithms from just the problem specification! An example and further
references are given here
http://thread.gmane.org/gmane.comp.lang.haskell.cafe/42316/focus=42320
Concerning matrix chain multiplication, here is my implementation. Note
the use of telling names and algebraic data types; there is no need to
get lost in a maze of twisty little indexes, all alike.
import Data.List
import Data.Array
import Data.Ord
type Dimension = (Int,Int)
type Cost = Int
-- data type representing a parenthesization,
-- caches cost to calculate and dimension of the result matrix
data Parens = Mul !Cost Dimension Parens Parens
| Matrix Dimension deriving (Show)
-- retrieve cached vallues
cost :: Parens -> Cost
cost (Mul c _ _ _) = c
cost (Matrix _) = 0
dimension :: Parens -> Dimension
dimension (Mul _ d _ _) = d
dimension (Matrix d) = d
-- smart constructor
mul :: Parens -> Parens -> Parens
mul x y = Mul (cost x + cost y + n*m*p) (n,p) x y
where
(n,m,p) = (fst $ dimension x, snd $ dimension x,
snd $ dimension y)
-- dynamic programming algorithm
solve :: [Int] -> Parens
solve matrices = chain 1 n
where
n = length matrices - 1
dimensions = array (1,n) . zip [1..] $
zip (init matrices) (tail matrices)
chain = memoize n chain'
chain' i j
| i == j = Matrix (dimensions ! i)
| otherwise = best [mul (chain i k) (chain (k+1) j)
| k <- [i..j-1] ]
best = minimumBy (comparing cost)
-- memoize a function on a "square" [1..n] x [1..n]
memoize :: Int -> (Int -> Int -> a) -> (Int -> Int -> a)
memoize n f = \i j -> table ! (i,j)
where
table = array ((1,1),(n,n)) $
[((i,j), f i j) | i <- [1..n], j <- [1..n]]
Example output:
*Main> cost $ solve [10,100,5,50,1]
1750
I didn't need to debug this code, because it's obviously correct. Put
differently, instead of spending my effort on debugging, I have spent it
on making the solution elegant.
Regards,
Heinrich Apfelmus
--
http://apfelmus.nfshost.com
------------------------------
Message: 5
Date: Wed, 7 Jul 2010 11:51:30 +0200
From: Daniel Fischer <daniel.is.fisc...@web.de>
Subject: Re: [Haskell-beginners] Re: Dynamic Programming in Haskell
To: beginners@haskell.org
Message-ID: <201007071151.31142.daniel.is.fisc...@web.de>
Content-Type: text/plain; charset="utf-8"
On Wednesday 07 July 2010 11:30:28, Heinrich Apfelmus wrote:
>
> I didn't need to debug this code, because it's obviously correct. Put
> differently, instead of spending my effort on debugging, I have spent it
> on making the solution elegant.
>
Well done.
Chapeau!
>
> Regards,
> Heinrich Apfelmus
>
------------------------------
Message: 6
Date: Wed, 7 Jul 2010 15:50:43 +0300
From: Markus L?ll <markus.l...@gmail.com>
Subject: Re: [Haskell-beginners] what's a proper way to make a Set
typeclass? and why is it not done already?
To: beginners@haskell.org
Message-ID:
<aanlktils_3mwx81l3hfbvpqhpnz465doml-ocysek...@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
A few more questions. (I've been trying to make a list instance of a set)
1. Which is better to use:
> class (Eq elem) => Set setTC elem where ...
> instance (Eq elem) => Set [] elem where ...
or
> class (Eq elem) => Set set elem | set -> elem where ...
> instance (Eq elem) => Set [elem] elem where ...
(I do need the functional dependency, because the set type, as being
parametric, defines its element type?)
The second one seemd easier to use at first when writing type
signatures, but after a little fiddling, I got the other one working
also.
2. Is there a way to make another instance for list as a set, when the
element besides being instance of Eq, but also then of Ord (instead of
just writing another class called OrdSet)?
This is to take advandage of the Ord class -- like having a sorted
list of elements. Then, for inserting or checking for membership, I
could look only as far as I need in the list.
3. Lastly, I was thinking, that for elements from Enum types could use
a bit-array for even faster set operations.
Should I make other types (like lists and trees) instances of the Set
class, or, instead, make a set type, and have it have many
constructors for many data-structures?
Markus
------------------------------
Message: 7
Date: Wed, 7 Jul 2010 13:53:57 +0100
From: Magnus Therning <mag...@therning.org>
Subject: Re: [Haskell-beginners] Some beginning questions for Haskell
To: Liu shuping <lsp....@gmail.com>
Cc: beginners@haskell.org
Message-ID:
<aanlktimv90dnmelacxyh5qyynxj9xrqodom7sxeo6...@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
On Wed, Jul 7, 2010 at 05:04, Liu shuping <lsp....@gmail.com> wrote:
> Hi,
> I am new to Haskell, currently I am doing .Net development on windows
> platform. I began to know about Haskell for the reason when I knew some C#
> lambda features come from functional language. I am interested in Haskell
> from the very beginning when I saw it.
> For I am really a very beginner, I get some basic questions:
> 1. Can you have some very general information to explain why use Haskell or
> functional language.
http://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pdf
> 2. Is it a right choice of Haskell if I want to develop some geology
> software which mainly doing some huge numerical computation which takes long
> long time?
My gut tells me that the language isn't as important as the available hardware
in this case. The second issue is that you'll need efficient implementations
of the math you make use of; I suspect you won't find highly optimised math
libraries specialising in this area within the Haskell community (please prove
me wrong).
You can of course always create Haskell bindings for a good library; writing
the control logic in Haskell and leave the number crunching to something
that's closer to HW maybe.
> 3. How about user interface, is Haskell capable to build application with
> complex user interface? or should I just use Haskell to build the core
> engine and user other language to build the user interface?
It depends on what kind of user interface you want. For desktop applications
you have the GTK bindings. But that will only look native on Gnome systems.
Web UIs are popular, there are web frameworks for Haskell, but arguably the UI
wouldn't be written in Haskell but rather in javascript.
You might want to have a look at flapjax[1] if you decide to go the
web-UI route.
> 4. Is Haskell cross-platform? I mean if the Haskell source code is "code
> once and build everywhere?"
This is more a question about libraries rather than the language itself. The
basic libraries are x-platform, except of course for the platform-specific
parts.
> 5. Are there any successful applications built with Haskell? Â they can give
> me a direct scene of what Haskell can do.
Depending on what you mean by "successful":
⢠ghc
⢠darcs
⢠happstack
⢠leksah
/M
[1] http://www.flapjax-lang.org/
--
Magnus Therning (OpenPGP: 0xAB4DFBA4)
magnusï¼ therningï¼org Jabber: magnusï¼ therningï¼org
http://therning.org/magnus identi.ca|twitter: magthe
------------------------------
Message: 8
Date: Wed, 7 Jul 2010 14:28:18 +0100
From: Brent Yorgey <byor...@seas.upenn.edu>
Subject: Re: [Haskell-beginners] what's a proper way to make a Set
typeclass? and why is it not done already?
To: beginners@haskell.org
Message-ID: <20100707132818.ga1...@seas.upenn.edu>
Content-Type: text/plain; charset=iso-8859-1
On Wed, Jul 07, 2010 at 03:50:43PM +0300, Markus Läll wrote:
> A few more questions. (I've been trying to make a list instance of a set)
>
>
> 1. Which is better to use:
>
> > class (Eq elem) => Set setTC elem where ...
> > instance (Eq elem) => Set [] elem where ...
>
> or
>
> > class (Eq elem) => Set set elem | set -> elem where ...
> > instance (Eq elem) => Set [elem] elem where ...
>
> (I do need the functional dependency, because the set type, as being
> parametric, defines its element type?)
Right. You could also use an associated type family, like this:
class (Eq (Elem set)) => Set set where
type Elem set :: *
...
add :: Elem set -> set -> set
...
instance (Eq elem) => Set [elem] where
type Elem [elem] = elem
...
> The second one seemd easier to use at first when writing type
> signatures, but after a little fiddling, I got the other one working
> also.
The second one gives you a bit more flexibility, since you can have
Set instances for non-parametric types. For example, with the second
you could have
instance Set ByteString Word8 where
...
>
> 2. Is there a way to make another instance for list as a set, when the
> element besides being instance of Eq, but also then of Ord (instead of
> just writing another class called OrdSet)?
There is, but it requires using newtype wrappers, like so:
newtype OrdList a = OrdList [a] -- lists with elements having an Ord
constraint
instance (Ord elem) => Set (OrdList elem) elem where
...
Of course, that does mean you'll have to wrap and unwrap OrdList
constructors a bit, but there are nice ways of dealing with that.
> 3. Lastly, I was thinking, that for elements from Enum types could use
> a bit-array for even faster set operations.
>
> Should I make other types (like lists and trees) instances of the Set
> class, or, instead, make a set type, and have it have many
> constructors for many data-structures?
I should think the first option would be nicer.
-Brent
------------------------------
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 25, Issue 22
*****************************************
