[Haskell-beginners] 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 <rasen.dubi at gmail.com> 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 <bob at redivi.com
> <javascript:;>> wrote:
> > On Monday, June 15, 2015, derek riemer <driemer.riemer at gmail.com
> <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
> > Beginners at haskell.org <javascript:;>
> > http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
> >
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org <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.html>