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: splicing (Alexey Shmalko)
2. Re: splicing (Bob Ippolito)
3. Re: splicing (Alexey Shmalko)
4. Syntax of Complex (Shishir Srivastava)
5. Re: Syntax of Complex (Bob Ippolito)
----------------------------------------------------------------------
Message: 1
Date: Mon, 15 Jun 2015 07:29:15 +0300
From: Alexey Shmalko <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] splicing
Message-ID:
<CAFC2PC4F14xpnx95oV_k=baDU9mbdZAF=7yg0nzueuw+ype...@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
Just a quick not that slicing vectors is O(1), it doesn't copy anything.
I would prefer not passing start and end indexes and use slicing because:
1) You won't need a wrapper function
2) It's mentally easier to think in terms of halves ("ok, now do
binary search in the right half")
On Mon, Jun 15, 2015 at 7:16 AM, Bob Ippolito <[email protected]> wrote:
> On Monday, June 15, 2015, derek riemer <[email protected]> wrote:
>>
>> Hi guys,
>> As a newby to haskell, I was curious, what is the best way to splice an
>> array or do things in the middle?
>> For example, binary search requires i do in sudocode
>> define binary search array target.
>> Find middle element.
>> If target is middle element then return target
>> else if target < middle element then
>> binary search array[0:target]
>> else
>> binary search array[target:end]
>>
>> How can I get this splicing with haskell?
>> I can't just use head here.
>> I can't do array!!n: where n is some number.
>
>
> You probably shouldn't use lists for binary search, since indexing a list is
> linear time. Binary searching a list is slower than a linear search.
> However, if you must, you can use splitAt for that purpose.
>
> Where you should really be looking for Array-like uses are Data.Vector or
> Data.Array. The former is probably better suited for this use case.
>
> You should also consider adding arguments to the search function for start
> and end indexes, rather than slicing the array itself. That's the more
> traditional way to implement it.
>
> -bob
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
------------------------------
Message: 2
Date: Mon, 15 Jun 2015 07:05:30 +0200
From: Bob Ippolito <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] splicing
Message-ID:
<CACwMPm9o7VzDi-UdkVACCkXHa_aZQHMpd8PQ5wt=iw=tca-...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Which works ok (still a higher constant factor, O(1) isn't free) if you
want a Bool or Maybe a answer, but if you want the index of the element
you're searching for then slicing is not the best way.
On Monday, June 15, 2015, Alexey Shmalko <[email protected]> wrote:
> Just a quick not that slicing vectors is O(1), it doesn't copy anything.
>
> I would prefer not passing start and end indexes and use slicing because:
> 1) You won't need a wrapper function
> 2) It's mentally easier to think in terms of halves ("ok, now do
> binary search in the right half")
>
> On Mon, Jun 15, 2015 at 7:16 AM, Bob Ippolito <[email protected]
> <javascript:;>> wrote:
> > On Monday, June 15, 2015, derek riemer <[email protected]
> <javascript:;>> wrote:
> >>
> >> Hi guys,
> >> As a newby to haskell, I was curious, what is the best way to splice an
> >> array or do things in the middle?
> >> For example, binary search requires i do in sudocode
> >> define binary search array target.
> >> Find middle element.
> >> If target is middle element then return target
> >> else if target < middle element then
> >> binary search array[0:target]
> >> else
> >> binary search array[target:end]
> >>
> >> How can I get this splicing with haskell?
> >> I can't just use head here.
> >> I can't do array!!n: where n is some number.
> >
> >
> > You probably shouldn't use lists for binary search, since indexing a
> list is
> > linear time. Binary searching a list is slower than a linear search.
> > However, if you must, you can use splitAt for that purpose.
> >
> > Where you should really be looking for Array-like uses are Data.Vector or
> > Data.Array. The former is probably better suited for this use case.
> >
> > You should also consider adding arguments to the search function for
> start
> > and end indexes, rather than slicing the array itself. That's the more
> > traditional way to implement it.
> >
> > -bob
> >
> > _______________________________________________
> > Beginners mailing list
> > [email protected] <javascript:;>
> > http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
> >
> _______________________________________________
> Beginners mailing list
> [email protected] <javascript:;>
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150615/b3a1ff1c/attachment-0001.html>
------------------------------
Message: 3
Date: Mon, 15 Jun 2015 08:28:43 +0300
From: Alexey Shmalko <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] splicing
Message-ID:
<CAFC2PC7PB-egS4E_RWOruhwPGK=jb5tx8qr7d6lxhr-vkkz...@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
Yes, indeed. I forget that we're usually searching for index :)
On Mon, Jun 15, 2015 at 8:05 AM, Bob Ippolito <[email protected]> wrote:
> Which works ok (still a higher constant factor, O(1) isn't free) if you want
> a Bool or Maybe a answer, but if you want the index of the element you're
> searching for then slicing is not the best way.
>
>
> On Monday, June 15, 2015, Alexey Shmalko <[email protected]> wrote:
>>
>> Just a quick not that slicing vectors is O(1), it doesn't copy anything.
>>
>> I would prefer not passing start and end indexes and use slicing because:
>> 1) You won't need a wrapper function
>> 2) It's mentally easier to think in terms of halves ("ok, now do
>> binary search in the right half")
>>
>> On Mon, Jun 15, 2015 at 7:16 AM, Bob Ippolito <[email protected]> wrote:
>> > On Monday, June 15, 2015, derek riemer <[email protected]> wrote:
>> >>
>> >> Hi guys,
>> >> As a newby to haskell, I was curious, what is the best way to splice an
>> >> array or do things in the middle?
>> >> For example, binary search requires i do in sudocode
>> >> define binary search array target.
>> >> Find middle element.
>> >> If target is middle element then return target
>> >> else if target < middle element then
>> >> binary search array[0:target]
>> >> else
>> >> binary search array[target:end]
>> >>
>> >> How can I get this splicing with haskell?
>> >> I can't just use head here.
>> >> I can't do array!!n: where n is some number.
>> >
>> >
>> > You probably shouldn't use lists for binary search, since indexing a
>> > list is
>> > linear time. Binary searching a list is slower than a linear search.
>> > However, if you must, you can use splitAt for that purpose.
>> >
>> > Where you should really be looking for Array-like uses are Data.Vector
>> > or
>> > Data.Array. The former is probably better suited for this use case.
>> >
>> > You should also consider adding arguments to the search function for
>> > start
>> > and end indexes, rather than slicing the array itself. That's the more
>> > traditional way to implement it.
>> >
>> > -bob
>> >
>> > _______________________________________________
>> > 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
>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
------------------------------
Message: 4
Date: Mon, 15 Jun 2015 12:03:24 +0100
From: Shishir Srivastava <[email protected]>
To: beginners <[email protected]>
Subject: [Haskell-beginners] Syntax of Complex
Message-ID:
<CALe5RTv2YLKWJtG9cV=zbpbxlauwga9pgt6_pzwne7xpnrx...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Hi,
The Data.Complex package defines the new data type 'Complex' as
----------
data Complex a = !a :+ !a
-------
Where ':+' is an infix operator. I don't however understand the usage of
'!' in front of the type variable 'a'. What exactly is the purpose of '!' ?
Any help would be appreciated.
Thanks,
Shishir Srivastava
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150615/5136adf9/attachment-0001.html>
------------------------------
Message: 5
Date: Mon, 15 Jun 2015 13:18:22 +0200
From: Bob Ippolito <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Syntax of Complex
Message-ID:
<cacwmpm-ztvbyk4s8sdkzuwws79boq4of1s-bteh+mwn1rys...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
On Monday, June 15, 2015, Shishir Srivastava <[email protected]>
wrote:
> Hi,
>
> The Data.Complex package defines the new data type 'Complex' as
>
> ----------
>
> data Complex a = !a :+ !a
>
> -------
>
> Where ':+' is an infix operator. I don't however understand the usage of
> '!' in front of the type variable 'a'. What exactly is the purpose of '!' ?
>
'!' is a strictness annotation. This means that when the value is forced to
weak-head normal form (by pattern matching, BangPatterns, or seq), then the
fields with the ! will also be forced to weak-head normal form.
See also:
http://chimera.labs.oreilly.com/books/1230000000929/ch02.html#sec_par-eval-whnf
https://hackhands.com/lazy-evaluation-works-haskell/
-bob
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150615/4b6e81c9/attachment-0001.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 84, Issue 24
*****************************************
