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 |
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 |
In reply to this post by derek riemer
On Monday, June 15, 2015, derek riemer <[hidden email]> wrote:
Hi guys, 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 |
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 |
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. _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners |
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 |
Free forum by Nabble | Edit this page |