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