[Haskell-beginners] splicing

Alexey Shmalko rasen.dubi at gmail.com
Mon Jun 15 04:29:15 UTC 2015


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
>


More information about the Beginners mailing list