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: Longest common subsequence (Daniel Seidel)
2. Re: Longest common subsequence (Brent Yorgey)
3. folds again -- myCycle (7stud)
4. Re: Integer factorization (Heinrich Apfelmus)
5. Re: folds again -- myCycle (Daniel Fischer)
6. Re: Re: Integer factorization (Francesco Bochicchio)
----------------------------------------------------------------------
Message: 1
Date: Fri, 13 Mar 2009 13:00:17 +0100
From: Daniel Seidel <[email protected]>
Subject: Re: [Haskell-beginners] Longest common subsequence
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=UTF-8; format=flowed
Leslie P. Polzer wrote:
> Hi,
>
> after the factorial function I tried to write my second Haskell
> program, tackling the longest common subsequence algorithm:
>
> lcsList :: [a] -> [a] -> [a]
> lcsList [] _ = []
> lcsList _ [] = []
> lcsList (x:xs) (y:ys) = if x == y
> then lcsList xs ys
> else
> let lcs1 = lcsList x:xs ys
> lcs2 = lcsList xs y:ys
> in if (length lcs1) > (length lcs2)
> then lcs1
> else lcs2
>
> main = do
> putStrLn("Result: " show lcsList [1,2,3] [1,3])
>
> GHC has several problems with it:
>
> lcs.hs:4:27:
> Could not deduce (Eq a) from the context ()
> arising from a use of `==' at lcs.hs:4:27-32
> Possible fix:
> add (Eq a) to the context of the type signature for `lcsList'
>
> I understand that I need to specify that type 'a' needs to
> be a derived type of something that can be compared, but
> how do I specify this in the code?
>
> On a related note, how can I make the function more flexible,
> to discern between case-sensitive and case-insensitive string
> comparison, for example?
>
> In Lisp I would just write this lambda list:
>
> (defun lcs-list (list1 list2 &key (test #'eql))
> ...)
>
> and it would allow me to specify the test but use some sensible
> default if I don't.
>
>
> And two other errors which I don't quite get:
>
> lcs.hs:7:50:
> Couldn't match expected type `[a] -> [[a1] -> [a1]]'
> against inferred type `[a]'
> In the second argument of `(:)', namely `xs ys'
> In the expression: lcsList x : xs ys
> In the definition of `lcs1': lcs1 = lcsList x : xs ys
>
> lcs.hs:8:33:
> Occurs check: cannot construct the infinite type: a = [a]
> When generalising the type(s) for `lcs2'
> In the expression:
> let
> lcs1 = lcsList x : xs ys
> lcs2 = lcsList xs y : ys
> in if (length lcs1) > (length lcs2) then lcs1 else lcs2
>
> in if (length lcs1) > (length lcs2) then lcs1 else lcs2
>
> Can you help me with that?
>
> Thanks,
>
> Leslie
>
>
Hi,
there are some mistakes inside.
a compiling version (not sure, if it does what you expect) is
lcsList :: Eq a => [a] -> [a] -> [a]
lcsList [] _ = []
lcsList _ [] = []
lcsList (x:xs) (y:ys) = if x == y
then x : lcsList xs ys
else
let lcs1 = lcsList (x:xs) ys
lcs2 = lcsList xs (y:ys)
in if (length lcs1) > (length lcs2)
then lcs1
else lcs2
main = do
putStrLn("Result: " ++ show (lcsList [1,2,3] [1,3]))
There were some common mistakes in your version:
1. type signature needs the type class Eq a, to ensure that you can
compare the elements (function (==) is present)
2. function application binds stronger than cons (:), therefore lcsList
x:xs ys means (lcsList x): (xs ys) NOT lcsList (x:xs) ys
3. in the main function concatination of strings (++) and braces around
the argument of show where missing, which leds to
parsing: "Result" as a function with show, lcsList, [1,2,3] and [1,3]
as arguments.
Greetings,
Daniel.
------------------------------
Message: 2
Date: Fri, 13 Mar 2009 09:47:37 -0400
From: Brent Yorgey <[email protected]>
Subject: Re: [Haskell-beginners] Longest common subsequence
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
On Fri, Mar 13, 2009 at 11:58:17AM +0100, Leslie P. Polzer wrote:
>
> On a related note, how can I make the function more flexible,
> to discern between case-sensitive and case-insensitive string
> comparison, for example?
One way you could do this by making a newtype wrapper around Char and
creating a new Eq instance for it, like so:
import Data.Char (toLower)
newtype CaseInsensitive = CI Char
instance Eq CaseInsensitive where
(CI c1) == (CI c2) = toLower c1 == toLower c2
toCI :: String -> [CaseInsensitive]
toCI = map CI
fromCI :: [CaseInsensitive] -> String
fromCI = map (\(CI c) -> c)
-- now to do a case-insensitive LCS search you can just say something like
fromCI (lcsList (toCI "BriCK") (toCI "bARk"))
Of course, you could also write another version of lcsList which takes
an explicit equality predicate, like the lisp version you described,
but there's no way to have 'optional arguments' in Haskell. But this
actually isn't too bad:
-- a generic version
lcsListGen :: (a -> a -> Bool) -> [a] -> [a] -> [a]
lcsListGen eq xs ys = ... LCS algorithm here, using eq for comparison ...
-- the less general version using an Eq constraint can just be
-- implemented in terms of the above, passing in (==) for the equality test.
lcsList :: (Eq a) => [a] -> [a] -> [a]
lcsList = lcsListGen (==)
-Brent
------------------------------
Message: 3
Date: Sat, 14 Mar 2009 07:57:57 +0000 (UTC)
From: 7stud <[email protected]>
Subject: [Haskell-beginners] folds again -- myCycle
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
I spent a long time working on a solution for an exercise in RWH: if you can,
use foldr to mimic haskell's cycle function. At first, I wondered whether
it was even possible. Then I worked on some ideas, and finally I came up with
a solution. Surprisingly, my solution ended up being very simple:
myCycle [] = []
myCycle xs = helperFunc xs [1..]
where helperFunc ys foldrXs = foldr accFunc [] foldrXs
where accFunc _ acc = ys ++ acc
I tested it out, and it worked like a charm:
*Main> let x = myCycle [1, 2, 3]
*Main> take 2 x
[1,2]
*Main> take 10 x
[1,2,3,1,2,3,1,2,3,1]
*Main> take 30 x
[1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3]
After re-examining my solution, I decided that this line:
--where accFunc _ acc = ys ++ acc
read better like this:
--where accFunc _ acc = acc ++ ys
The altered function returns a list just fine. But when I use take on the
list, I get a stack overflow. What is being thunked in both cases?
Thanks.
------------------------------
Message: 4
Date: Sat, 14 Mar 2009 09:39:18 +0100
From: Heinrich Apfelmus <[email protected]>
Subject: [Haskell-beginners] Re: Integer factorization
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
Colin Paul Adams wrote:
>>>>>> "Heinrich" == Heinrich Apfelmus <[email protected]> writes:
>
> Heinrich> Abstraction is the one driving force for very short
> Heinrich> names. For example, take the definition of foldr
>
> Heinrich> foldr f z [] = z foldr f z (x:xs) = f x (foldr f z
> Heinrich> xs)
>
> Heinrich> Since this function is polymorphic, so f , z and the xs
> Heinrich> can be anything, using more "descriptive" variable names
> Heinrich> is simply not possible; the key point of fold is its
> Heinrich> generality.
>
> Wouldn't unit be a better descriptive name than z?
I have never heard of a unit in relation to fold , I'm afraid. Monoids
and groups have units, as do physicists and a few other mathematical
structures.
While z is indeed quite often the unit of a monoid, for instance in
sum = foldr (+) 0
product = foldr (*) 1
concat = foldr (++) []
it doesn't have to be the unit of a monoid.
Regards,
apfelmus
--
http://apfelmus.nfshost.com
------------------------------
Message: 5
Date: Sat, 14 Mar 2009 11:47:44 +0100
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] folds again -- myCycle
To: 7stud <[email protected]>, [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
Am Samstag, 14. März 2009 08:57 schrieb 7stud:
> I spent a long time working on a solution for an exercise in RWH: if you
> can, use foldr to mimic haskell's cycle function. At first, I wondered
> whether it was even possible. Then I worked on some ideas, and finally I
> came up with a solution. Surprisingly, my solution ended up being very
> simple:
>
> myCycle [] = []
> myCycle xs = helperFunc xs [1..]
> where helperFunc ys foldrXs = foldr accFunc [] foldrXs
> where accFunc _ acc = ys ++ acc
>
> I tested it out, and it worked like a charm:
>
> *Main> let x = myCycle [1, 2, 3]
> *Main> take 2 x
> [1,2]
> *Main> take 10 x
> [1,2,3,1,2,3,1,2,3,1]
> *Main> take 30 x
> [1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3]
>
> After re-examining my solution, I decided that this line:
>
> --where accFunc _ acc = ys ++ acc
>
> read better like this:
>
> --where accFunc _ acc = acc ++ ys
>
> The altered function returns a list just fine. But when I use take on the
> list, I get a stack overflow. What is being thunked in both cases?
Let us rewrite the definition a little (looking only at the case for nonempty
lists):
Variant 1:
myCycle xs = foldr leftAdd [] [1 .. ]
where
leftAdd _ acc = xs ++ acc
foldr leftAdd [] [1 .. ]
~> leftAdd 1 (foldr leftAdd [] [2 .. ])
~> xs ++ (foldr leftAdd [] [2 .. ])
~> xs ++ (leftAdd 2 (foldr leftAdd [] [3 .. ]))
~> xs ++ (xs ++ (foldr leftAdd [] [3 .. ]))
~> xs ++ (xs ++ (xs ++ (xs ++ ...)))
Variant 2:
myCycle xs = foldr rightAdd [] [1 .. ]
where
rightAdd _ acc = acc ++ xs
foldr rightAdd [] [1 .. ]
~> rightAdd 1 (foldr rightAdd [] [2 .. ])
~> (foldr rightAdd [] [2 .. ]) ++ xs
~> (rightAdd 2 (foldr rightAdd [] [3 .. ])) ++ xs
~> ((foldr rightAdd [] [3 .. ]) ++ xs) ++ xs
~> (((... ++ xs) ++ xs) ++ xs
So in the first variant, where the cycled list is added to the front of the
accumulator, the first elements of the list can be accessed before the
accumulator is evaluated.
In the second variant, the front of the result list is the accumulator, so it
has to be evaluated before any part of the result can be accessed.
Unfortunately, the front is an infinite nesting of concatenations, so its
evaluation never finishes.
The thing is that leftAdd is lazy in its second argument, while rightAdd is
strict in it.
If the accumulation function used in foldr is strict in its second argument,
before any part of the result can be accessed, the whole list has to be
traversed (which obviously will never finish for infinite lists).
Let us rewrite it a little more.
Obviously, it doesn't matter which list is passed into
foldr leftAdd []
, as long as it's infinite. So instead of passing [1 .. ], let us pass a
simpler infinite list, say
ones = 1:ones
(or ones = repeat 1).
Then the evaluation becomes
foldr leftAdd [] ones
~> foldr leftAdd [] (1:ones)
~> leftAdd 1 (foldr leftAdd [] ones)
~> xs ++ (foldr leftAdd [] ones)
foldr rightAdd [] ones
~> foldr rightAdd [] (1:ones)
~> rightAdd 1 (foldr rightAdd [] ones)
~> (foldr rightAdd [] ones) ++ xs
So variant 1 amounts to
myCycle xs = let ys = xs ++ ys in ys
and variant 2 to
myCycle2 xs = let ys = ys ++ xs in ys
Now it should be easy to see why the first works, but not the second.
And from the rewriting, we can read off another representation of cycle as a
fold.
We have, for all lists ks, ms:
ks ++ ms = foldr (:) ms ks
So we can write variant 1 as the snappy
myCycle xs = let ys = foldr (:) ys xs in ys
>
> Thanks.
HTH,
Daniel
------------------------------
Message: 6
Date: Sat, 14 Mar 2009 12:21:22 +0100
From: Francesco Bochicchio <[email protected]>
Subject: Re: [Haskell-beginners] Re: Integer factorization
To: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
2009/3/13 Heinrich Apfelmus <[email protected]>
> Francesco Bochicchio wrote:
> > Heinrich Apfelmus wrote:
> >>
> >> Stylistically, one usually uses shorter variable names in Haskell.
> >
> > <beginner rant>
> ...
> > </beginner rant>
> >
> > Rant apart, I notice that in my own excercises I tend to shorten names,
> so
> > maybe there is a reason for that.
> > Nevertheless readability tends to be a big issue in languages used in IT
> > industry, and my feeling is that haskell
> > tends to err on the laconic side of the balance.
>
> The goal is of course to make code readable, that's why I recommend
> short names. :D
>
> Abstraction is the one driving force for very short names. For example,
> take the definition of foldr
>
> foldr f z [] = z
> foldr f z (x:xs) = f x (foldr f z xs)
>
> Since this function is polymorphic, so f , z and the xs can be
> anything, using more "descriptive" variable names is simply not
> possible; the key point of fold is its generality.
Ok but one could still hint at their structure or purpose:
foldr function value (x:xs) = function x ( foldr function value xs )
I believe this would give a little more information to the casual reader.
>
>
> A second, and my main reason for short names, or rather against long
> names, is that names should be to the point. None of the names
>
> newPrimes
> topPrime
> doFactors
> doFilter
>
> accurately describe the object they represent. The primes are not "new",
> the prime is not "on top". The "do" is a prefix does not carry a meaning
> either, it just conveys that doFactors has something to do with
> factors . This is best expressed by making doFactors a local
> definition in the where-block of factors .
I agree that well-documented shared name conventions are better than
roll-your-own.
(x:xs) is one example of such convention, although I tend to adopt slight
variations
like (n:nums) for list of numbers and (ch:chars) for list of characters.
But roll-your-own is still better than cryptic.
>
>
> The name eratosthenesFilter is ok, but since there is no other
> eratosthenes around, no meaning is lost by shortening it to simply
> eratosthenes . Not to mention that the conventional term is "sieve", not
> "filter". The documentation has to elaborate on it anyway.
>
> The generality of the name num hints that a single letter name is
> preferable.
>
> The names that I think are great because they are to the point are
>
> factors
> primes
>
> I have some resistance to use nouns for functions. In the imperative world,
nouns are for
variables, verbs are for functions. I know that in pure functional
programming there is not such a thing
as variables, but still I would reserve nouns for function parameters and
bound expressions. Hence if I have a function that
find factors, I would call it findFactors rather than just factors.
One such example of misnaming - from a beginner point of view - is the
length function in prelude: if it was called
count, I believe more beginners would have realized that works by actually
counting the elements of
a list and not by accessing to some already available 'property' of the
list.
>
>
> > Out of curiosity, there is any reason why you called the auxiliary
> function
> > 'go' ?
>
> Convention. Often, an auxiliary function that does basically the same
> thing as the main function factors but with an extra parameter will be
> named factors' . The apostrophe has the drawback that it's easy to
> forget, so some people now name such auxiliary functions go instead.
>
>
I tend to use _ instead of '. Is more visible and keep conveying the idea
that the auxiliary function
is just a slight variation of the main one.
>
>
> Regards,
> apfelmus
>
Ciao
------
FB
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://www.haskell.org/pipermail/beginners/attachments/20090314/c0692edd/attachment.htm
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 9, Issue 15
****************************************
