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: Just how unsafe is unsafe (Austin Seipp)
2. Re: Appending to a list (Francesco Bochicchio)
3. Re: Appending to a list (Adrian Neumann)
4. Re: Appending to a list (Heinrich Apfelmus)
5. Re: Just how unsafe is unsafe (Austin Seipp)
6. Re: Installing packages (Tymur Porkuian)
7. Re: Installing packages (Krzysztof Skrz?tnicki)
----------------------------------------------------------------------
Message: 1
Date: Sun, 08 Feb 2009 01:45:45 -0600
From: Austin Seipp <[email protected]>
Subject: Re: [Haskell-beginners] Just how unsafe is unsafe
To: The Haskell-Beginners Mailing List <[email protected]>
Message-ID: <[email protected]>
Content-Type: text/plain; charset=UTF-8
Excerpts from Andrew Wagner's message of Thu Feb 05 15:11:17 -0600 2009:
> My question is, to what extent is this true?
You can completely destroy the soundness of the type system:
import Data.IORef
import System.IO.Unsafe
import Control.Monad
cast :: a -> b
cast x = f where
f = unsafePerformIO $ do
writeIORef r [x]
b <- liftM head $ readIORef r
return b
Austin
------------------------------
Message: 2
Date: Sun, 8 Feb 2009 09:24:30 +0100
From: Francesco Bochicchio <[email protected]>
Subject: Re: [Haskell-beginners] Appending to a list
To: beginners <[email protected]>
Message-ID:
<[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
2009/2/7 Cory Knapp <[email protected]>
<nice explanation on : operator - always useful>
>
> Does that help, or did I miss the point?
>
> Ok, I'll try to be more clear with an example: the following function -
which surely can be written in better way - takes a list and a predicate and
builds two lists. a list of lists of consecutive elements that satisfy the
predicate and a list of separators, i.e. of elements that does not satisfy
the predicate.
That is: groups odd [1,3,2,5,9,6] -> [[1,3],[5,9]], [2,6]
The function uses another function, groupWhile, which works like takeWhile
but returns also the rest of the list.
Now, from the way the function works, it shoud build the two result lists by
appending new elements to them.
But, as you said, appending is expensive in haskell, so instead I build the
lists using (:), which gives me the list
in reverse order, and then I use the 'final step' of the function - the base
case of the recursion - to reverse the
result. If I understand lazyness, this should be a low-cost operation
because it does not actual build a reversed
list, but only make the list to be 'consumed' from the tail.
Now, this trick is not mine: I read it somewhere on internet (I
can'tremember where), so I was asking if it is classified among the 'neat
tricks' or among the 'ugly hacks' :-)
Here is the code I was referring to:
groups :: (a->Bool)-> [a] -> ([[a]],[a])
groups f lst = groups_ f ([],[]) lst where
groups_ f (gs,seps) [] = (reverse gs, reverse seps)
groups_ f (gs,seps) [a] = if (f a)
then ( reverse ( [a]:gs), reverse seps )
else ( reverse gs , reverse (a:seps) )
groups_ f (gs, seps) lst = groups_ f (g:gs, r:seps) est
where
(g, (r:est)) = groupWhile f lst
Ciao
-------
FB
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://www.haskell.org/pipermail/beginners/attachments/20090208/6396d453/attachment-0001.htm
------------------------------
Message: 3
Date: Sun, 8 Feb 2009 09:26:41 +0100
From: Adrian Neumann <[email protected]>
Subject: Re: [Haskell-beginners] Appending to a list
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="us-ascii"
Yes, appending to the tail of a list is an expensive operation.
You may ask yourself why there is no pointer to the end of a list.
That's because the end is in general not known (e.g. if the list is
produced by a computation, or if it's infinite).
However if you know up front that your list will be finite and you
don't rely on lazyness you may want to use a Data.Sequence instead
> http://www.haskell.org/ghc/docs/latest/html/libraries/containers/
Data-Sequence.html
Cheers,
Adrian
Am 07.02.2009 um 21:29 schrieb Francesco Bochicchio:
> Hi all,
>
> in my haskell exercises I often build list by appending values at
> the end.
> But I read somewhere that in haskell this is inefficient since
> there is no
> 'pointer to the tail of the list'. I've also seen some example of
> recursive
> functions which build the list tail-first and then in the base case
> of the
> recursion returns the reverse of the accumulated results, counting
> on the fact
> that in haskell 'reverse list' just means 'consume the list from
> the tail'.
>
> Just out of curiosity (I have no need to speed up my little
> programs with which I try to teach myself
> some haskell): is this a consolidated pattern? And are append
> really expensive?
>
> Ciao
> -------
> FB
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
-------------- next part --------------
A non-text attachment was scrubbed...
Name: PGP.sig
Type: application/pgp-signature
Size: 194 bytes
Desc: Signierter Teil der Nachricht
Url :
http://www.haskell.org/pipermail/beginners/attachments/20090208/0e9cb17f/PGP-0001.bin
------------------------------
Message: 4
Date: Sun, 08 Feb 2009 11:57:47 +0100
From: Heinrich Apfelmus <[email protected]>
Subject: [Haskell-beginners] Re: Appending to a list
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
Francesco Bochicchio wrote:
> But, as you said, appending is expensive in haskell
We can say how expensive. Namely, fully evaluating
xs ++ ys
takes O(length xs) time. Always appending an element at the end will
lead to something like
(..((([1] ++ [2]) ++ [3]) ++ [4]) ++ ..) ++ [n]
which will take O(n^2) time instead of linear time. This is probably
best demonstrated with the following two implementations of reverse
reverse1 [] = []
reverse1 (x:xs) = reverse1 xs ++ [x]
reverse2 xs = go [] xs
where
go ys [] = ys
go ys (x:xs) = go (x:ys) xs
The first runs in quadratic time while second runs in linear time.
> so instead I build the lists using (:), which gives me the list in
> reverse order, and then I use the 'final step' of the function - the
> base case of the recursion - to reverse the result. If I understand
> laziness, this should be a low-cost operation because it does not
> actual build a reversed list, but only make the list to be
> 'consumed' from the tail.
No, reverse has nothing to do with laziness and still costs O(n) time.
It's just that building the list in linear time and then reversing it in
linear time is cheaper than building the list in quadratic time.
> Here is the code I was referring to:
>
> groups :: (a->Bool)-> [a] -> ([[a]],[a])
> groups f lst = groups_ f ([],[]) lst where
> groups_ f (gs,seps) [] = (reverse gs, reverse seps)
> groups_ f (gs,seps) [a] = if (f a)
> then ( reverse ( [a]:gs), reverse seps )
> else ( reverse gs , reverse (a:seps) )
> groups_ f (gs, seps) lst = groups_ f (g:gs, r:seps) est
> where
> (g, (r:est)) = groupWhile f lst
While using reverse instead of appending at the end of the list is a
good idea, not building the list in reverse at all is much better.
First, let me restate your code as
groups p xs = go ([],[]) xs
where
go (gs,seps) xs = let (g,rest) = span p xs in
case rest of
r:est -> go (g:gs, r:seps) est
[] -> (reverse (g:gs), reverse seps)
The groupWhile function can be found in the Prelude, it's called span
. This function groups differs from yours, for instance we have
groups odd [2,2,2] == ([[],[],[],[]],[2,2,2])
groups odd [1,2] == ([[1],[]],[2])
groups odd [1,1] == ([[1,1]],[])
By the way, your code crashes in the last case.
Now, let's reformulate it so that the result won't be built in reverse.
The key is to eliminate the unnecessary accumulating parameter and work
with the result of the recursive call to groups directly:
groups p xs = let (g,rest) = span p xs in
case rest of
r:est -> let (gs,seps) = groups p est in (g:gs,r:seps)
[] -> ([g], [])
I'd say that this is the canonical implementation.
In case you wrote this function to split strings, have a look at
http://hackage.haskell.org/cgi-bin/hackage-scripts/package/split
Regards,
apfelmus
--
http://apfelmus.nfshost.com
------------------------------
Message: 5
Date: Sun, 08 Feb 2009 13:43:46 -0600
From: Austin Seipp <[email protected]>
Subject: Re: [Haskell-beginners] Just how unsafe is unsafe
To: The Haskell-Beginners Mailing List <[email protected]>
Message-ID: <[email protected]>
Content-Type: text/plain; charset=UTF-8
Excerpts from Austin Seipp's message of Sun Feb 08 01:45:45 -0600 2009:
> ... code ...
>
> Austin
*smacks head*
import Data.IORef
import System.IO.Unsafe
import Control.Monad
cast :: a -> b
cast x = f where
f = unsafePerformIO $ do
writeIORef r [x]
b <- liftM head $ readIORef r
return b
r = unsafePerformIO $ newIORef []
------------------------------
Message: 6
Date: Mon, 9 Feb 2009 00:27:57 +0200
From: Tymur Porkuian <[email protected]>
Subject: Re: [Haskell-beginners] Installing packages
To: "Brandon S. Allbery KF8NH" <[email protected]>
Cc: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
>> I'm trying to install wxcore-0.11.0 using Cabal. I've downloaded it
>> from
>> http://hackage.haskell.org/cgi-bin/hackage-scripts/package/wxcore-0.11.0,
>> unpacked and tried to follow instructions from
>> http://haskell.org/haskellwiki/Cabal/How_to_install_a_Cabal_package,
>> but this is what I'm getting:
>>
>> D:\libraries\wxcore-0.11.0>runhaskell Setup configure
>> Setup: sh: runGenProcess: does not exist (No such file or directory)
>>
>> What does this mean?
>
> On Windows it usually means that the package has a "configure" shell script
> and therefore requires that Cygwin or MSYS be installed.
I have installed Cygwin, and still getting the exact same error.
Should something else be done after installing it?
------------------------------
Message: 7
Date: Mon, 9 Feb 2009 00:09:50 +0100
From: Krzysztof Skrz?tnicki <[email protected]>
Subject: Re: [Haskell-beginners] Installing packages
To: [email protected]
Cc: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=UTF-8
On Sun, Feb 8, 2009 at 23:27, Tymur Porkuian <[email protected]> wrote:
>>> I'm trying to install wxcore-0.11.0 using Cabal. I've downloaded it
>>> from
>>> http://hackage.haskell.org/cgi-bin/hackage-scripts/package/wxcore-0.11.0,
>>> unpacked and tried to follow instructions from
>>> http://haskell.org/haskellwiki/Cabal/How_to_install_a_Cabal_package,
>>> but this is what I'm getting:
>>>
>>> D:\libraries\wxcore-0.11.0>runhaskell Setup configure
>>> Setup: sh: runGenProcess: does not exist (No such file or directory)
>>>
>>> What does this mean?
>>
>> On Windows it usually means that the package has a "configure" shell script
>> and therefore requires that Cygwin or MSYS be installed.
>
> I have installed Cygwin, and still getting the exact same error.
> Should something else be done after installing it?
Are you running "cabal install" from within Cygwin prompt?
All best
Christopher SkrzÄtnicki
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 8, Issue 6
***************************************
