Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://mail.haskell.org/cgi-bin/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: Package access problem (Daniel Bergey)
2. Re: tower hanoi problem (Joel Neely)
3. Re: tower hanoi problem (Roelof Wobben)
----------------------------------------------------------------------
Message: 1
Date: Wed, 18 Feb 2015 13:23:35 +0000
From: Daniel Bergey <[email protected]>
To: Brandon Allbery <[email protected]>, The Haskell-Beginners
Mailing List - Discussion of primarily beginner-level topics related
to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Package access problem
Message-ID: <[email protected]>
Content-Type: text/plain
On 2015-02-18 at 02:15, Brandon Allbery <[email protected]> wrote:
> On Tue, Feb 17, 2015 at 9:13 PM, Gregory Guthrie <[email protected]> wrote:
>
>> <no location info>:
>>
>> Could not find module `Diagrams'
>>
>>
> "Diagrams" is not a module in any of the packages; it's just a point in the
> namespace under which the actual modules reside. I see for example at
> http://hackage.haskell.org/package/diagrams-core
Expanding on Brandon's answer, Diagrams.Prelude[1] is probably what you
want to import. You'll also need one of the Backends, to save files.
See for instance this minimal example: [2]
Footnotes:
[1]
http://hackage.haskell.org/package/diagrams-lib-1.2.0.8/docs/Diagrams-Prelude.html
[2] http://projects.haskell.org/diagrams/doc/manual.html#getting-started
------------------------------
Message: 2
Date: Wed, 18 Feb 2015 07:34:40 -0600
From: Joel Neely <[email protected]>
To: Dudley Brooks <[email protected]>, The Haskell-Beginners
Mailing List - Discussion of primarily beginner-level topics related
to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] tower hanoi problem
Message-ID:
<caeezxaj6jkngpbw4czvhnrgv9n7sp85amxwgq5weopxrhxp...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
I believe that the assertion that "*in the sequence *of lines in the
program* you have to state the base case(s) *first**" is a bit too strong,
although it is certainly correct to say that termination must be assured.
For (a very trivial) example:
dupEvens :: [Int] -> [Int]
dupEvens (n:ns)
| even n = n : n : dupEvens ns
| otherwise = n : dupEvens ns
dupEvens [] = []
which behaves as:
*Main> dupEvens [3,1,4,1,5,9,2,6]
[3,1,4,4,1,5,9,2,2,6,6]
*Main> dupEvens [0..5]
[0,0,1,2,2,3,4,4,5]
the base case for list recursion (the empty list) is stated last. That is
not a problem because the inductive case (non-empty list) contains a
pattern that won't match an empty list.
So I suggest modifying the beginners' advice to something like:
*When evaluating a function, Haskell considers the parts of the definition
in the order they are written, top-to-bottom, and uses the first one that
matches. So make sure that your left-hand sides (patterns or guards) are
precise enough to select the correct right-hand side is evaluated.*
The (trivial *and horrible*) example:
badDupEvens :: [Int] -> [Int]
badDupEvens ns
| even (head ns) = (head ns) : (head ns) : badDupEvens (tail ns)
| otherwise = (head ns) : badDupEvens (tail ns)
badDupEvens [] = []
violates that advice, and gets its just desserts:
*Main> badDupEvens [0..5]
[0,0,1,2,2,3,4,4,5*** Exception: Prelude.head: empty list
And, (again for us beginners) a good tip to help avoid such things is to
place:
{-# OPTIONS_GHC -Wall #-}
at the beginning of each source file. This allows the compiler to complain
at me:
trivialdemo.hs:12:1: Warning:
Pattern match(es) are overlapped
In an equation for ?badDupEvens?: badDupEvens [] = ...
which (if I'm paying attention) makes me think about my patterns a bit more.
For what it's worth, I tend to try to make my patterns and guards precise
enough that they can prevent divergence without too much reliance on
lexical ordering. I picked up that habit almost 40 years ago, thanks to
Dijkstra's "guarded command" notation in *A Discipline of Programming*.
I don't know to what extent that is (or isn't) idiomatic in the Haskell
community.
On Tue, Feb 17, 2015 at 1:42 PM, Dudley Brooks <[email protected]>
wrote:
> Um ... To the other people giving hints: Don't forget that in the
> sequence *of lines in the program* you have to state the base case(s)
> *first*, certainly in Haskell, which goes through the lines in order, until
> it finds a match.
>
> That's what I meant when I said "first do the base case(s), then the
> rest": first *in the program order*, if not necessarily in the conceptual
> structure. So for the depth-first binary tree which Joel Neely pointed
> out, *first* you must deal with the base case that the node being looked at
> is actually a leaf; *only then* can you deal with the fact that in general
> the algorithm has the structure <process left descendants><process this
> node><process right descendants>.
>
> So if you try <move stack off of bottom><move bottom><place stack on
> bottom>, the first part will either enter an endless loop or will generate
> an error, because it doesn't have a base case. (No pun on "base" intended.)
>
>
> On 2/17/15 4:05 AM, Joel Neely wrote:
>
> ?Let's tweak your answers? just a bit, calling the three pegs the
> "source", "goal", and "spare" pegs:
>
> On Tue, Feb 17, 2015 at 5:23 AM, Roelof Wobben <[email protected]> wrote:
>
>> - Where do I move the bottom (largest disk) ?
>>
>> To the last peg, which do not contain any disk then
>> ? .
>>
>
> From the source peg to the goal peg, which will
> /must
> not contain any disks.?
>
>
>> ?
>>
>>
>> - What must happen before I can move the bottom disk ?
>>
>> I have to move the disk which above that disk.
>>
>
> Move everything else from ____ to ____.?
>
>
>>
>> - What must happen after I move the bottom disk ?
>>
>> All the other disk must be placed above that disk.
>>
>
> ? Move everything else from ____ to ____.?
>
>
> ?So more questions/hints:
>
> 1. How do you fill in the blanks?
> 2. How do you put the three statements in order?
> 3. How many disks does each statement talk about?
>
>
> -jn-
> ?
>
>
>
> --
> Beauty of style and harmony and grace and good rhythm depend on
> simplicity. - Plato
>
>
> _______________________________________________
> Beginners mailing
> [email protected]http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
>
--
Beauty of style and harmony and grace and good rhythm depend on simplicity.
- Plato
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150218/9d50caf4/attachment-0001.html>
------------------------------
Message: 3
Date: Wed, 18 Feb 2015 17:35:20 +0100
From: Roelof Wobben <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] tower hanoi problem
Message-ID: <[email protected]>
Content-Type: text/plain; charset=windows-1252; format=flowed
Oke,
Im thinking of this way
hanoi 3 source between end
hanoi 1 source _ end = [ (source, end)]
hanoi n source between end = hanoi (n-1) xxxx
print move
somehow.
Roelof
Dudley Brooks schreef op 18-2-2015 om 17:19:
> There are three *locations*. But there is only one *thing* -- only
> *one at a time*, that is, namely whichever one you are moving on any
> given move, be it a disc or an entire stack.
>
> On 2/17/15 11:10 PM, Roelof Wobben wrote:
>> That part I understand already.
>>
>> The only thing I do not see is what the base case in this exercise is
>> because you are working with 3 things instead of 1 for example a list.
>>
>> As a example reversing a list recursive
>>
>> the base case is the not reversed list is empty.
>>
>>
>> Roelof
>>
>>
>>
>> Dudley Brooks schreef op 18-2-2015 om 8:04:
>>> On 2/17/15 10:56 PM, Dudley Brooks wrote:
>>>> On 2/16/15 7:06 PM, Doug McIlroy wrote:
>>>>>> My way of working is one problem at the time.
>>>>>> So first solve the itterate one and after that I gonna try to
>>>>>> solve the
>>>>>> recursion one.
>>>>>> Otherwise I get confused.
>>>>> This is the crux of the matter. You must strive to think those
>>>>> thoughts
>>>>> in the opposite order. Then you won't get confused.
>>>>>
>>>>> Recursion takes a grand simplifying view: "Are there smaller
>>>>> problems of
>>>>> the same kind, from the solution(s) of which we could build a
>>>>> solution of
>>>>> the problem at hand?" If so, let's just believe we have a solver
>>>>> for the
>>>>> smaller problems and build on them. This is the recursive step.
>>>>>
>>>>> Of course this can't be done when you are faced with the smallest
>>>>> possible problem. Then you have to tell directly how to solve
>>>>> it. This is the base case.
>>>>>
>>>>> [In Hanoi, the base case might be taken as how to move a pile
>>>>> of one disc to another post. Even more simply, it might be how
>>>>> to move a pile of zero discs--perhaps a curious idea, but no more
>>>>> curious than the idea of 0 as a counting number.]
>>>>>
>>>>> A trivial example: how to copy a list (x:xs) of arbitrary length.
>>>>> We could do that if we knew how to copy the smaller list tail, xs.
>>>>> All we have to do is tack x onto the head of the copy. Lo, the recipe
>>>>> copy (x:xs) = x : copy xs
>>>>> Final detail: when the list has no elements, there is no smaller
>>>>> list to copy. We need another rule for this base case. A copy
>>>>> of an empty list is empty:
>>>>> copy [] = []
>>>>>
>>>>> With those two rules, we're done. No iterative reasoning about
>>>>> copying all the elements of the list. We can see that afterward,
>>>>> but that is not how we got to the solution.
>>>>>
>>>>> [It has been suggested that you can understand recursion thus
>>>>> > Do the first step. Then (to put it very dramatically)
>>>>> > do *everything else* in *a single step*!
>>>>> This point of view works for copy, and more generally for
>>>>> "tail recursion", which is trivially transformable to iteration.
>>>>> It doesn't work for Hanoi, which involves a fancier recursion
>>>>> pattern. The "smaller problem(s)" formulation does work.]
>>>>
>>>> I simplified it (or over-dramatized it) to the point of
>>>> not-quite-correctness. I was trying to dramatize the point of how
>>>> surprising the idea of recursion is, when you first encounter it
>>>> (because I suspected that the OP had not yet "grokked" the elegance
>>>> of recursion) -- and remembering my own Aha! moment at recursive
>>>> definitions and proofs by induction in high school algebra, back
>>>> when the only "high-level" programming language was assembly. I
>>>> see that I gave the mistaken impression that that's the *only* kind
>>>> of recursive structure. What I should have said, less dramatically, is
>>>>
>>>> Do the base case(s)
>>>> Then do the recursion -- whatever steps that might involve,
>>>> including possibly several recursive steps and possibly even
>>>> several single steps, interweaved in various possible orders.
>>>>
>>>> You can't *start* with the recursion, or you'll get either an
>>>> infinite loop or an error.
>>>>
>>>> I wouldn't quite call the conversion of tail-recursion to iteration
>>>> trivial, exactly ... you still have to *do* it, after all! And
>>>> when I did CS in school (a long time ago), the equivalence had only
>>>> fairly recently been recognized. (By computer language designers,
>>>> anyway. Maybe lambda-calculus mathematicians knew it long before
>>>> that.) Certainly the idea that compilers could do it automatically
>>>> was pretty new. If it were *completely* trivial, it would have
>>>> been recognized long before! ;^)
>>>>
>>>> If you're younger you probably grew up when this idea was already
>>>> commonplace. Yesterday's brilliant insight is today's trivia!
>>>
>>> BTW, since, as you and several others point out, the recursive
>>> solution of Towers of Hanoi does *not* involve tail recursion,
>>> that's why it's all the more surprising that there actually is a
>>> very simple iterative solution, almost as simple to state as the
>>> recursive solution, and certainly easier to understand and follow by
>>> a novice or non-programmer, who doesn't think recursively.
>>>>
>>>>> In many harder problems a surefire way to get confused is to
>>>>> try to think about the sequence of elementary steps in the final
>>>>> solution. Hanoi is a good case in point.
>>>>>
>>>>> Eventually you will come to see recursion as a way to confidently
>>>>> obtain a solution, even though the progress of the computation is
>>>>> too complicated to visualize. It is not just a succinct way to
>>>>> express iteration!
>>>>>
>>>>> Doug McIlroy
>>>>> _______________________________________________
>>>>> Beginners mailing list
>>>>> [email protected]
>>>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>>>
>>>
>>> _______________________________________________
>>> Beginners mailing list
>>> [email protected]
>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>>
>>
>
>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 80, Issue 41
*****************************************
