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. Thompson Exercise 9.13 (dan portin)
2. Re: why is something different within a function when it
comes out? (prad)
3. Re: Thompson Exercise 9.13 (Daniel Fischer)
4. Re: Re: why is something different within a function when it
comes out? (Daniel Fischer)
5. My first functioning haskell project - a steganography
utility (Tim Cowlishaw)
6. Re: [Haskell-cafe] lists of arbitrary depth (Richard O'Keefe)
7. A difficult package (Ben Wise)
----------------------------------------------------------------------
Message: 1
Date: Wed, 14 Jul 2010 11:55:17 -0700
From: dan portin <[email protected]>
Subject: [Haskell-beginners] Thompson Exercise 9.13
To: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
Hi,
I am new to Haskell (and programming). Thompson's exercise 9.13 in *Craft
of Functional Programming *gave me trouble. Searching the list archives, I
saw people define init (xs), last (xs), and so on, in a variety of complex
ways (using the Maybe monad, using fairly complex post-processing). This
seems to be a hard problem for beginners; at least, it was rather hard for
me.
The problem is to define the Prelude functions *init* and *last* using *
foldr*. After a while, I came up with:
-- *Exercise 9.13*: Use foldr (f, s, xs) to give definitions of the prelude
functions
-- unzip, last, and init.
-- Clearly,
-- [(x, y), (x1, y1)] = (x, y) : (x1, y1) : ([], [])
-- foldr f ([], []) ((x, y):(x1, y1):[]) = f (x, y) (f (x1, y1) ([],
[]))
-- Hence, f (x, y) (xs, ys) must equal (x:xs, y:ys) for any xs, ys.
unzip :: [(a, b)] -> ([a], [b])
unzip xys = foldr f ([], []) xys
where f :: (a, b) -> ([a], [b]) -> ([a], [b])
f (x, y) (xs, ys) = (x:xs, y:ys)
*last* :: [a] -> a
last xs = head $ foldr f [] xs
where f :: a -> [a] -> [a]
f x [] = [x]
f x ys = ys ++ [x]
*init* :: [a] -> [a]
init xs = tail $ foldr f [] xs
where f :: a -> [a] -> [a]
f x [] = [x]
f x (y:xs) = y : x : xs
Now, these seemed to be hard questions. So, I have three questions: (1) are
these correct? They work on test cases, and I *did* do some quick proofs.
They seem okay. (2) Is there a way to eliminate the post-processing of the
lists (i.e., *head* in *last* and *tail* in *init*)? (3) Why the complex
answers in the list archives? Am I missing something?
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://www.haskell.org/pipermail/beginners/attachments/20100714/b70db061/attachment-0001.html
------------------------------
Message: 2
Date: Wed, 14 Jul 2010 13:41:00 -0700
From: prad <[email protected]>
Subject: [Haskell-beginners] Re: why is something different within a
function when it comes out?
To: [email protected]
Message-ID: <20100714134100.7fe3f...@gom>
Content-Type: text/plain; charset=ISO-8859-1
On Wed, 14 Jul 2010 10:54:22 +0200
Chaddaï Fouché <[email protected]> wrote:
> In fact xtract could be written :
> > xtract p c = (c =~ p :: [[String]]) !! 0 !! 1
this is exactly what i was trying to do but couldn't figure out how to
write it because i couldn't get my head around the return. it seems so
simple when someone else does it. :D
thx for your explanations chaddai and you too michael.
this (as well as some crude attempts i've used earlier) work nicely on
text enclosed in single lines, but find nothing for multiple lines. in
python, there is a dotall or re.S flag so that things can be searched
for over \n in the text. i can't figure out how to do this here.
i looked at
http://hackage.haskell.org/packages/archive/regex-tdfa/1.1.3/doc/html/Text-Regex-TDFA.html
but am having difficulty figuring things out from the documentation -
and there doesn't seem to be any multiline feature.
surely there is some way to do this!
also, python had a re.sub so you can replace things using regex
searchs. how would you go about doing that in haskell?
--
In friendship,
prad
... with you on your journey
Towards Freedom
http://www.towardsfreedom.com (website)
Information, Inspiration, Imagination - truly a site for soaring I's
------------------------------
Message: 3
Date: Wed, 14 Jul 2010 23:02:28 +0200
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] Thompson Exercise 9.13
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="utf-8"
On Wednesday 14 July 2010 20:55:17, dan portin wrote:
> Hi,
>
> I am new to Haskell (and programming). Thompson's exercise 9.13 in
> *Craft of Functional Programming *gave me trouble. Searching the list
> archives, I saw people define init (xs), last (xs), and so on, in a
> variety of complex ways (using the Maybe monad,
Using Maybe isn't really complex, and for the implementations I sort of
remember, the fact that Maybe is a Monad didn't play a role.
> using fairly complex
> post-processing). This seems to be a hard problem for beginners; at
> least, it was rather hard for me.
Yes, it's not easy before you're familiar with foldr.
If you don't try too hard to avoid any post-processing, it's not incredibly
hard, though.
>
> The problem is to define the Prelude functions *init* and *last* using *
> foldr*. After a while, I came up with:
>
> -- *Exercise 9.13*: Use foldr (f, s, xs) to give definitions of the
> prelude functions
> -- unzip, last, and init.
>
> -- Clearly,
> -- [(x, y), (x1, y1)] = (x, y) : (x1, y1) : ([], [])
That last one is a typo,
[(x,y),(x1,y1)] = (x,y) : (x1,y1) : []
> -- foldr f ([], []) ((x, y):(x1, y1):[]) = f (x, y) (f (x1, y1) ([],
> []))
> -- Hence, f (x, y) (xs, ys) must equal (x:xs, y:ys) for any xs, ys.
Yup.
>
> unzip :: [(a, b)] -> ([a], [b])
> unzip xys = foldr f ([], []) xys
> where f :: (a, b) -> ([a], [b]) -> ([a], [b])
> f (x, y) (xs, ys) = (x:xs, y:ys)
However, this has a small problem,
take 3 . fst $ unzip [(i,i+1) | i <- [0 .. ]]
won't return with that definition of unzip.
The reason is subtle,
f (x,y) (xs,ys) = (x:xs,y:ys)
must inspect its second argument to match it with the pattern (xs,ys).
To do that, it must evaluate the nested call to f first.
f (x,y) (f (x1,y1) ([],[]))
~> match (xs,ys) with f (x1,y1) ([],[])
~> evaluate f (x1,y1) ([],[])
~> match (xs,ys) with ([],[])
~> matches
~> (x1:[], y1:[])
~> matches
~> (x:x1:[], y:y1:[])
Thus it needs to traverse the entire list before it can start assembling
the result.
To avoid that, so the result can be assembled from the start of the list,
you need to make the pattern match on the second argument lazy,
f (x,y) ~(xs,ys) = (x:xs,y:ys)
or
f (x,y) p = (x : fst p, y : snd p)
Now
f (x,y) (f (x1,y1) ([],[]))
~> let (xs,ys) = f (x1,y1) ([],[]) in (x:xs, y:ys)
and assembling the result starts immediately.
The tilde on a pattern makes that pattern irrefutable, the passed argument
is bound to the pattern immediately and it will only be
deconstructed/evaluated when needed.
It's sort of a "trust me, the argument will have that form, don't check it"
message to the compiler/interpreter. Of course it will usually crash hard
if the passed argument doesn't have the promised form.
In this case, it can't crash very hard, because the type checker doesn't
allow anything but a pair to be passed as an argument, and a pair can only
be (blah, blub) or _|_ (bottom). But if you use a tilde-pattern for a
multi-constructor type, you better get it right.
>
> *last* :: [a] -> a
> last xs = head $ foldr f [] xs
> where f :: a -> [a] -> [a]
> f x [] = [x]
> f x ys = ys ++ [x]
last xs = head (reverse xs), yes, it's correct, but not very pretty.
And not very efficient since it builds a left-associated nest of (++)
applications and needs to pattern match to decide which branch to take.
last (1:2:3:4:[])
~> head $ foldr f [] (1:2:3:4:[])
~> head $ f 1 (f 2 (f 3 (f 4 [])))
~> head $ f 1 (f 2 (f 3 [4]))
~> head $ f 1 (f 2 ([4] ++ [3]))
~> head $ f 1 (([4] ++ [3]) ++ [2])
~> head $ ((([4] ++ [3]) ++ [2]) ++ [1]
a) in the second branch of f, you don't actually need to concatenate,
f x [] = [x]
f _ ys = ys
works too, but is faster.
b) you can get much faster by delaying the pattern match,
f x ys = (case ys of { [] -> x; y:_ -> y }) : []
>
> *init* :: [a] -> [a]
> init xs = tail $ foldr f [] xs
> where f :: a -> [a] -> [a]
> f x [] = [x]
> f x (y:xs) = y : x : xs
Correct too, but again not very efficient since it has to find the last
element and bubble it to the front.
Much faster:
import Data.Maybe (fromMaybe)
init' :: [a] -> [a]
init' = fromMaybe (error "init': empty list") . foldr f Nothing
where
f x mb = Just $ case mb of
Just xs -> x:xs
Nothing -> []
By delaying the pattern match on the Maybe until after the constructor is
applied, we can start building the output with minimal delay (we only need
to look whether there's a next list element to decide whether to cons it to
the front or not).
>
> Now, these seemed to be hard questions. So, I have three questions: (1)
> are these correct? They work on test cases, and I *did* do some quick
> proofs. They seem okay.
They are correct for finite lists, unzip and init above won't return on
infinite lists (last shouldn't, so that's correct for infinite lists too).
They are not, strictly speaking, correct for infinite lists. But that is
way beyond beginner territory :)
> (2) Is there a way to eliminate the
> post-processing of the lists (i.e., *head* in *last* and *tail* in
> *init*)?
Not in a clean way.
Let us consider last first.
Suppose we had
last xs = foldr f z xs
without post-processing.
Since foldr f z [] = z and last [] = error "Prelude.last: empty list",
we must have z = error "...".
Now last (... x:[]) = x and
foldr f z (... x:[]) = ... (f x z)
So f x y = y if y is not error "..." and f x (error "...") = x, that means
f would have to find out whether its second argument is a specific error
and return its first argument in that case, otherwise its second argument.
It's possible to do that, but very unclean.
For init, the situation is similar, the value for the empty list case
supplied to foldr must be an error and the combining function needs to know
whether its second argument is an error and do things accordingly.
> (3) Why the complex answers in the list archives? Am I missing
> something?
Don't know. In part, because beginners didn't find the easiest ways, I
suppose, in part because it's not too easy to give efficient
implementations with foldr.
------------------------------
Message: 4
Date: Wed, 14 Jul 2010 23:12:47 +0200
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] Re: why is something different within
a function when it comes out?
To: [email protected]
Cc: prad <[email protected]>
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
On Wednesday 14 July 2010 22:41:00, prad wrote:
> also, python had a re.sub so you can replace things using regex
> searchs. how would you go about doing that in haskell?
There's subRegex in Text.Regex in the regex-compat package (don't know if
it's also provided in other packages).
------------------------------
Message: 5
Date: Tue, 13 Jul 2010 14:35:45 +0100
From: Tim Cowlishaw <[email protected]>
Subject: [Haskell-beginners] My first functioning haskell project - a
steganography utility
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
Hey there all,
I've just completed my first functional haskell project - a simple utility for
steganography - hiding messages within the least significant bit of another
sort of data file.
Therefore, I was wondering if any of you had any pointers about how I could
refactor or otherwise improve my code? Any input would be greatly appreciated -
whether howling great errors or smaller points of "good haskell style". In
particular, I'd be really interested in whether my type declarations are
correct - for instance, whether I have been to specific or not specific enough
in specifying the types of my functions (Integral vs Int, etc).
In addition, I keep feeling that my Steganograph 'smells like' a monad and/or
functor , as it 'wraps around' a message - however, I'm having trouble defining
quite how I could achieve construct a monadic type representing a steganograph.
Is my hunch incorrect, or is there a way of doing this that I haven't yet
discovered?
The sources is here: http://gist.github.com/473862
Cheers,
Tim
------------------------------
Message: 6
Date: Wed, 14 Jul 2010 11:20:07 +1200
From: "Richard O'Keefe" <[email protected]>
Subject: [Haskell-beginners] Re: [Haskell-cafe] lists of arbitrary
depth
To: <[email protected]>
Cc: [email protected], [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=US-ASCII; format=flowed; delsp=yes
On Jul 13, 2010, at 9:00 PM, Christopher Done wrote:
> On 13 July 2010 10:58, vadali <[email protected]> wrote:\
>>
>> i want to define a function which takes as a parameter a list which
>> can
>> contain other lists, eg. [1,[2,3],[4,[5,6]]]
What would the type of a list like that be?
What you _can_ do is
data List_Or t = Item t | List [List_Or t]
deriving (Eq, Ord, Show)
and have a "list" like
ell :: List_Or Int
ell = List [Item 1, List [Item 2, Item 3], List [Item 4,
List [Item 5, Item 6]]]
>> how would i define a function that can iterate through the items so
>> (in this
>> example)
>> iter1 = 1
>> iter2 = [2,3]
>> iter3 = [4,[5,6]]
>>
Then you can write functions like
iter n (List x) = head (drop (n-1) x)
with examples
*Main> iter 1 ell
Item 1
*Main> iter 2 ell
List [Item 2,Item 3]
*Main> iter 3 ell
List [Item 4,List [Item 5,Item 6]]
>> ( can i do that without using the Tree data type? )
This basically _is_ a tree data type, even if not THE Tree
data type. That's because nested lists are trees.
>
------------------------------
Message: 7
Date: Wed, 14 Jul 2010 13:20:09 -0400
From: "Ben Wise" <[email protected]>
Subject: [Haskell-beginners] A difficult package
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain;charset=iso-8859-1
Folks,
I'm trying to work through Conrad Barski's Haskell tutorial,
http://www.lisperati.com/haskell/, and I've run into a difficult package
problem. I've googled around for two days, but nothing seems to work.
Basically, I can not get it recognize matchRegex, mkRegex, and similar.
They are all in the Text.Regex.Posix package, and version 0.94.1 is
installed according to 'cabal list regex'. The 'import Text.Regex.Posix'
line compiles just fine, so it is finding the package: it just doesn't
find the symbols in it ?!
But (under all four combinations of command line ghc or Leksah on Windows
7 or Ubuntu), it keeps trying to use the 'base' version, not posix. At
least, that's what 'ghc -v main.hs' seems to be saying. In Leksah, adding
some of the suggested build dependencies fixed earlier problems with
importing the Text and Random things, but adding 'regex-compat' as
suggested did not help.
Has anyone else gotten CB's tutorial to work?
Any suggestions as to how to get Text.Regex.Posix imported?
--
Ben Wise, PhD
0xCAF514E1
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 25, Issue 33
*****************************************
