Re: [Haskell-beginners] splicing

15 Jun 2015


      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