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: repetition (Daniel Fischer)
2. Re: repetition (Luca Ciciriello)
3. Re: Further constraining types (Thomas)
4. Looking for alternative practices suggestions (Michael Litchard)
5. Re: Looking for alternative practices suggestions
(Christopher Done)
6. Problems with Database (Gary Klindt)
7. Re: Looking for alternative practices suggestions (Mike Meyer)
8. Re: Problems with Database (Christopher Done)
9. Re: Further constraining types (Christopher Howard)
----------------------------------------------------------------------
Message: 1
Date: Thu, 4 Aug 2011 12:34:49 +0200
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] repetition
To: [email protected]
Message-ID: <[email protected]>
Content-Type: Text/Plain; charset="iso-8859-1"
On Thursday 04 August 2011, 11:44:31, Luca Ciciriello wrote:
> My mistake, I haven't specified that the starting list is ordered.
Then
map head . group
has the lower time complexity and does what you want.
Since nub has the type
nub :: Eq a => [a] -> [a]
its time complexity is O(n*d) where n is the length of the input list and d
the number of distinct elements in the list, so generally it has quadratic
behaviour.
map head . group has linear [O(n)] behaviour, thus scales better. But it
produces different output in general.
If the types you need to handle are instances of Ord, not only of Eq, you
can use that to write functions with a better time complexity.
Two very simple functions that remove duplicates and sort the input list
are
import Data.List
ordNub1 :: Ord a => [a] -> [a]
ordNub1 = map head . group . sort
import qualified Data.Set as S
ordNub2 :: Ord a => [a] -> [a]
ordNub2 = S.toAscList . S.fromList
-- currently at least, S.toList is the same as S.toAscList,
-- but that's not guaranteed, although unlikely to change
Both have O(n*log d) time complexity, but generally ordNub2 is faster.
If you want the order in which the distinct elements appear in the input
list to be preserved, like nub does, you can use
import qualified Data.Set as S
ordNub3 :: Ord a => [a] -> [a]
ordNub3 = go S.empty
where
go st (x:xs)
| x `S.member` st = go st xs
| otherwise = x : go (S.insert x st) xs
go _ [] = []
which also has O(n*log d) time complexity.
>
> Luca
>
> On Aug 4, 2011, at 11:39 AM, Thomas Davie wrote:
> > On 4 Aug 2011, at 10:36, Lyndon Maydwell wrote:
> >> nub
> >
> > Heh, our differing answers point out an ambiguity in the question.
> >
> > Luca, given [5,10,10,5] what is this function expected to produce?
> >
> > if you want [5,10] then nub is correct.
> > if you want [5,10,5] then map head . group is correct.
> >
> > Bob
------------------------------
Message: 2
Date: Thu, 4 Aug 2011 12:37:45 +0200
From: Luca Ciciriello <[email protected]>
Subject: Re: [Haskell-beginners] repetition
To: Daniel Fischer <[email protected]>
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
Ok, thanks.
Luca.
On Aug 4, 2011, at 12:34 PM, Daniel Fischer wrote:
> On Thursday 04 August 2011, 11:44:31, Luca Ciciriello wrote:
>> My mistake, I haven't specified that the starting list is ordered.
>
> Then
>
> map head . group
>
> has the lower time complexity and does what you want.
> Since nub has the type
>
> nub :: Eq a => [a] -> [a]
>
> its time complexity is O(n*d) where n is the length of the input list and d
> the number of distinct elements in the list, so generally it has quadratic
> behaviour.
> map head . group has linear [O(n)] behaviour, thus scales better. But it
> produces different output in general.
>
> If the types you need to handle are instances of Ord, not only of Eq, you
> can use that to write functions with a better time complexity.
> Two very simple functions that remove duplicates and sort the input list
> are
>
> import Data.List
>
> ordNub1 :: Ord a => [a] -> [a]
> ordNub1 = map head . group . sort
>
>
> import qualified Data.Set as S
>
> ordNub2 :: Ord a => [a] -> [a]
> ordNub2 = S.toAscList . S.fromList
> -- currently at least, S.toList is the same as S.toAscList,
> -- but that's not guaranteed, although unlikely to change
>
> Both have O(n*log d) time complexity, but generally ordNub2 is faster.
>
> If you want the order in which the distinct elements appear in the input
> list to be preserved, like nub does, you can use
>
> import qualified Data.Set as S
>
> ordNub3 :: Ord a => [a] -> [a]
> ordNub3 = go S.empty
> where
> go st (x:xs)
> | x `S.member` st = go st xs
> | otherwise = x : go (S.insert x st) xs
> go _ [] = []
>
> which also has O(n*log d) time complexity.
>
>>
>> Luca
>>
>> On Aug 4, 2011, at 11:39 AM, Thomas Davie wrote:
>>> On 4 Aug 2011, at 10:36, Lyndon Maydwell wrote:
>>>> nub
>>>
>>> Heh, our differing answers point out an ambiguity in the question.
>>>
>>> Luca, given [5,10,10,5] what is this function expected to produce?
>>>
>>> if you want [5,10] then nub is correct.
>>> if you want [5,10,5] then map head . group is correct.
>>>
>>> Bob
>
>
------------------------------
Message: 3
Date: Thu, 04 Aug 2011 12:49:11 +0200
From: Thomas <[email protected]>
Subject: Re: [Haskell-beginners] Further constraining types
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
> Once you've validated your user input though, nothing prevents you to
> have it return a Positive Int that you will guarantee can hold only
> positive integers, for example by using a smart constructor, and
> hiding the contructor in a separate module. You don't need dependant
> types for this.
Yes, but once you want to operate on that data you'll note the difference:
subtract :: Positive Int -> Positive Int -> ???
IIUC with dependent types you'll have a compile time guarantee, without
you'll have to test for errors at runtime.
Regards,
Thomas
------------------------------
Message: 4
Date: Thu, 4 Aug 2011 14:53:34 -0700
From: Michael Litchard <[email protected]>
Subject: [Haskell-beginners] Looking for alternative practices
suggestions
To: [email protected]
Message-ID:
<CAEzeKYr9pj=e2pv5887+7ukej5maze8-kftbzu07jk8oljs...@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
I'm finding that in more than one instance I pass a data structure to
a function, simply so that I can pass it to it's helper function. It
bugs me that I'm passing a value that isn't being used directly. This
seems wrong. Example: I have a "data URLSequence" that contains a way
to calculate the ip address of a URL. This gets passed to a helper
function that generates a particular URL, which then populates the
URLSequence. Is there a standard practice to avoid what I am talking
about? Or is this normal and I should accept it?
------------------------------
Message: 5
Date: Fri, 5 Aug 2011 00:02:24 +0200
From: Christopher Done <[email protected]>
Subject: Re: [Haskell-beginners] Looking for alternative practices
suggestions
To: Michael Litchard <[email protected]>
Cc: [email protected]
Message-ID:
<CAAJHNPBLhcV=PWYJ0Yf=6BbsFJawtgAGdP5=bur9pbpx+-l...@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
On 4 August 2011 23:53, Michael Litchard <[email protected]> wrote:
> I'm finding that in more than one instance I pass a data structure to
> a function, simply so that I can pass it to it's helper function. It
> bugs me that I'm passing a value that isn't being used directly. This
> seems wrong. Example: I have a "data URLSequence" that contains a way
> to calculate the ip address of a URL. This gets passed to a helper
> function that generates a particular URL, which then populates the
> URLSequence. Is there a standard practice to avoid what I am talking
> about? Or is this normal and I should accept it?
There is implicit parameters[1], but personally I bite the bullet in
cases like this as it doesn't happen so often.
[1]
http://www.haskell.org/ghc/docs/7.0.3/html/users_guide/other-type-extensions.html#implicit-parameters
------------------------------
Message: 6
Date: Fri, 05 Aug 2011 00:45:27 +0200
From: Gary Klindt <[email protected]>
Subject: [Haskell-beginners] Problems with Database
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Hi all,
I tried using a database via haskell. The following simple test program
could not be compiled via 'ghc Main.hs'. The output of ghc is:
Main.o: In function `s1pB_info':
(.text+0x6e): undefined reference to
`HDBCzmpostgresqlzm2zi2zi3zi3_DatabaseziHDBCziPostgreSQLziConnectionImpl_zdfIConnectionConnection_closure'
Main.o: In function `s1qt_info':
(.text+0x169): undefined reference to
`HDBCzmpostgresqlzm2zi2zi3zi3_DatabaseziHDBCziPostgreSQLziConnection_connectPostgreSQL_closure'
Main.o: In function `s1qt_info':
(.text+0x279): undefined reference to
`__stginit_HDBCzm2zi2zi7zi0_DatabaseziHDBC_'
Main.o: In function `s1qt_info':
(.text+0x283): undefined reference to
`__stginit_HDBCzmpostgresqlzm2zi2zi3zi3_DatabaseziHDBCziPostgreSQL_'
Main.o: In function `s1pB_info':
(.text+0x76): undefined reference to
`HDBCzm2zi2zi7zi0_DatabaseziHDBCziTypes_disconnect_info'
Main.o: In function `s1pC_srt':
(.data+0x4): undefined reference to
`HDBCzmpostgresqlzm2zi2zi3zi3_DatabaseziHDBCziPostgreSQLziConnectionImpl_zdfIConnectionConnection_closure'
Main.o: In function `s1qt_srt':
(.data+0x14): undefined reference to
`HDBCzmpostgresqlzm2zi2zi3zi3_DatabaseziHDBCziPostgreSQLziConnection_connectPostgreSQL_closure'
collect2: ld returned 1 exit status
Is this a bug? Or do I need to modify the configuration of my system?
If I load that module into ghci (':l Main') the compilation succeeds.
% ghc --version: 'The Glorious Glasgow Haskell Compilation System,
version 6.12.1'
% psql --version: 'psql (PostgreSQL) 8.4.8 contains support for
command-line editing'
I also wanted to try out MySQL. I stranded much earlier:
% cabal install database-hdbc-mysql: There is no such package, but
shouldn't there be one?
module Main where
import Database.HDBC
import Database.HDBC.PostgreSQL(connectPostgreSQL)
main :: IO ()
main = do
c <- connectPostgreSQL "host=localhost dbname=haskell user=gary
password=wasauchimmer"
disconnect c
return ()
I would be glad about help!
Greets
Gary
------------------------------
Message: 7
Date: Thu, 4 Aug 2011 15:47:23 -0700
From: Mike Meyer <[email protected]>
Subject: Re: [Haskell-beginners] Looking for alternative practices
suggestions
To: Michael Litchard <[email protected]>
Cc: [email protected]
Message-ID:
<CAD=7U2B5iT78D=eavlfrtdfp_8jj0scpbqc7+u0eqjhfe1w...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
On Thu, Aug 4, 2011 at 2:53 PM, Michael Litchard <[email protected]>wrote:
> I'm finding that in more than one instance I pass a data structure to
> a function, simply so that I can pass it to it's helper function. It
> bugs me that I'm passing a value that isn't being used directly. This
> seems wrong. Example: I have a "data URLSequence" that contains a way
> to calculate the ip address of a URL. This gets passed to a helper
> function that generates a particular URL, which then populates the
> URLSequence. Is there a standard practice to avoid what I am talking
> about? Or is this normal and I should accept it?
>
I think this is normal, and you should accept it. At least, assuming you're
using the result of the helper function somewhere. You could "solve" this by
hoisting the body of the helper function into the main function, but that
sort of defeats the point of having the helper function.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20110804/c1dadc24/attachment-0001.htm>
------------------------------
Message: 8
Date: Fri, 5 Aug 2011 00:53:22 +0200
From: Christopher Done <[email protected]>
Subject: Re: [Haskell-beginners] Problems with Database
To: Gary Klindt <[email protected]>
Cc: [email protected]
Message-ID:
<caajhnpbfro1y1-fonaw-knsxgbnjketrtdz_-mzi5+1n3y5...@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
On 5 August 2011 00:45, Gary Klindt <[email protected]> wrote:
> Hi all,
>
> I tried using a database via haskell. The following simple test program
> could not be compiled via 'ghc Main.hs'. The output of ghc is:
You need to tell ghc what libraries to link. Try ghc --make Main.hs
------------------------------
Message: 9
Date: Thu, 04 Aug 2011 18:52:03 -0800
From: Christopher Howard <[email protected]>
Subject: Re: [Haskell-beginners] Further constraining types
To: Haskell Beginners <[email protected]>
Message-ID: <[email protected]>
Content-Type: text/plain; charset=UTF-8; format=flowed
On 08/04/2011 12:03 AM, David Virebayre wrote:
> 2011/8/4 Christopher Howard<[email protected]>:
>> On 08/03/2011 09:23 PM, Brandon Allbery wrote:
>
>> This seems like a really significant issue for a functional programming
>> language. Am I eventually going to have to switch to Agda? My friends are
>> trying to convert me...
>
> I don't know Agda and what dependent type guarantee, but I don't see
> how they would prevent a user typing '-123' where you expect a
> positive number, so one way or another you will have to deal with
> input at runtime.
>
> Once you've validated your user input though, nothing prevents you to
> have it return a Positive Int that you will guarantee can hold only
> positive integers, for example by using a smart constructor, and
> hiding the contructor in a separate module. You don't need dependant
> types for this.
>
> David.
>
But users are not the only source of ints. For example, let's say I
wanted to do my own square function, with a type like so:
square :: Int -> Positive Int
So, I use the special constructor function in the implementation:
square x = validatePositive $ x * x
Great! now I have a function that returns Positive Ints, which can be
fed into any function that takes a Positive Int as its parameter.
Problem, though... how do I implement this special constructor in a way
that meets the criteria for completeness that I outlined earlier? A
validation function, by definition, allows for the possibility of
invalidation. So the type would have to be:
validatePositive :: Int -> Maybe (Positive Int)
But this means the type of square would have to be changed to
square :: Int -> Maybe (Positive Int)
...which is unacceptable. (I /know/ square /will/ always return an
positive integer, not that it /might/ do so!)
I could of course throw a "maybe"-style forced cast into the square
function, but that would defeat one of the fundamental principles of
what I'm trying to accomplish here.
Anyway, I think Brandon is right and the answer is in dependent types,
though to be honest I'm having real trouble decoding any of the
literature I've found so far.
--
frigidcode.com
theologia.indicium.us
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 38, Issue 8
****************************************
