splicing - Beginners - Haskell.org

newer
Syntax of Complex

splicing

derek riemer

14 Jun 2015 14 Jun '15

6:09 p.m.

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

Reply

Sign in to reply online Use email software

Show replies by date

Alexey Shmalko

15 Jun 15 Jun

12:12 a.m.

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 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 Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

Reply

Sign in to reply online Use email software

Bob Ippolito

12:16 a.m.

On Monday, June 15, 2015, derek 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

Reply

Sign in to reply online Use email software

Alexey Shmalko

12:29 a.m.

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 wrote:

On Monday, June 15, 2015, derek 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 Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

Reply

Sign in to reply online Use email software

Bob Ippolito

1:05 a.m.

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 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 Monday, June 15, 2015, derek riemer 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

On Mon, Jun 15, 2015 at 7:16 AM, Bob Ippolito javascript:;> wrote: 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 Beginners@haskell.org javascript:; http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@haskell.org javascript:; http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

Reply

Sign in to reply online Use email software

Alexey Shmalko

1:28 a.m.

Yes, indeed. I forget that we're usually searching for index :) On Mon, Jun 15, 2015 at 8:05 AM, Bob Ippolito 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 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 wrote:

...
On Monday, June 15, 2015, derek 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 Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

Reply

Sign in to reply online Use email software

3627

Age (days ago)

3628

Last active (days ago)

Download

5 comments

3 participants

tags

participants (3)

Alexey Shmalko
Bob Ippolito
derek riemer