splicing

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

splicing

derek riemer
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.

Thanks,
Derek
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: splicing

Alexey Shmalko
Hi, Derek!

Binary search algorithm requires random access, so you can't implement
it (efficiently) using lists. You'd better try using something as
vector [1]. It has both index and slice operations that work in O(1),
so implementing binary search is a breeze.

[1]: http://hackage.haskell.org/package/vector-0.10.12.3/docs/Data-Vector.html

On Mon, Jun 15, 2015 at 1:09 AM, derek riemer <[hidden email]> 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.
>
> Thanks,
> Derek
> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: splicing

Bob Ippolito
In reply to this post by derek riemer
On Monday, June 15, 2015, derek riemer <[hidden email]> 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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: splicing

Alexey Shmalko
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 <[hidden email]> wrote:

> On Monday, June 15, 2015, derek riemer <[hidden email]> 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
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: splicing

Bob Ippolito
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 <[hidden email]> 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 <<a href="javascript:;" onclick="_e(event, &#39;cvml&#39;, &#39;bob@redivi.com&#39;)">bob@...> wrote:
> On Monday, June 15, 2015, derek riemer <<a href="javascript:;" onclick="_e(event, &#39;cvml&#39;, &#39;driemer.riemer@gmail.com&#39;)">driemer.riemer@...> 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
> <a href="javascript:;" onclick="_e(event, &#39;cvml&#39;, &#39;Beginners@haskell.org&#39;)">Beginners@...
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
_______________________________________________
Beginners mailing list
<a href="javascript:;" onclick="_e(event, &#39;cvml&#39;, &#39;Beginners@haskell.org&#39;)">Beginners@...
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: splicing

Alexey Shmalko
Yes, indeed. I forget that we're usually searching for index :)

On Mon, Jun 15, 2015 at 8:05 AM, Bob Ippolito <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> wrote:
>> > On Monday, June 15, 2015, derek riemer <[hidden email]> 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
>> > [hidden email]
>> > http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>> >
>> _______________________________________________
>> Beginners mailing list
>> [hidden email]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
>
> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners