## digitalmars.D.learn - passing predicates to lowerBound, or alternatively, how lazy is map?

• Andrew Brown (24/24) Jun 11 2014 Hi there,
• John Colvin (5/30) Jun 11 2014 map is fully lazy.
• Andrew Brown (7/22) Jun 11 2014 Thanks for the reply, I'm going to have a lot of numbers though.
• John Colvin (3/28) Jun 11 2014 You are correct. assumeSorted and lowerBound will provide better
• Andrew Brown (10/12) Jun 11 2014 I'm sorry, one final question because I think I'm close to
• John Colvin (6/19) Jun 11 2014 map preserves the random access capabilities of it's source. An
• Andrew Brown (2/26) Jun 11 2014 That's great, thank you very much for taking the time to answer.
• Andrew Brown (11/11) Jun 11 2014 So I was hoping for a learning experience, and I got it. With a
• Andrew Brown (2/7) Jun 11 2014 That indexed command is perfect though, does the trick, thank you
• John Colvin (8/18) Jun 11 2014 For future reference: map applies its predicate in `front`,
"Andrew Brown" <aabrown24 hotmail.com> writes:
```Hi there,

The problem this question is about is now solved, by writing my
own binary search algorithm, but I'd like to ask it anyway as I
think I could learn a lot from the answers.

The problem was, given an array of numbers, double[] numbers, and
an ordering from makeIndex size_t[] order, I want to count how
many numbers are less than a number N. The obvious way would be
to use lowerBound from std.range, but I can't work out how to
pass it a predicate like "numbers[a] < b". Could someone explain
the template:

(SearchPolicy sp = SearchPolicy.binarySearch, V)(V value) if
(isTwoWayCompatible!(predFun, ElementType!Range, V));

The alternative way I thought to do it was to combine map with
lowerBound, i.e.:

map!(a => numbers[a])(order).assumeSorted
.lowerBound(N)
.length

value of order and then pass it to lowerBound, or could it work
to evaluate only those values asked by lowerBound? I guess
probably not, but could a function be composed that worked in
this way?

Thank you very much

Andrew
```
Jun 11 2014
"John Colvin" <john.loughran.colvin gmail.com> writes:
```On Wednesday, 11 June 2014 at 11:22:08 UTC, Andrew Brown wrote:
Hi there,

The problem this question is about is now solved, by writing my
own binary search algorithm, but I'd like to ask it anyway as I
think I could learn a lot from the answers.

The problem was, given an array of numbers, double[] numbers,
and an ordering from makeIndex size_t[] order, I want to count
how many numbers are less than a number N. The obvious way
would be to use lowerBound from std.range, but I can't work out
how to pass it a predicate like "numbers[a] < b". Could someone
explain the template:

(SearchPolicy sp = SearchPolicy.binarySearch, V)(V value) if
(isTwoWayCompatible!(predFun, ElementType!Range, V));

The alternative way I thought to do it was to combine map with
lowerBound, i.e.:

map!(a => numbers[a])(order).assumeSorted
.lowerBound(N)
.length

every value of order and then pass it to lowerBound, or could
it work to evaluate only those values asked by lowerBound? I
guess probably not, but could a function be composed that
worked in this way?

Thank you very much

Andrew

map is fully lazy.

However, if you've already got the sorted indices in `order`, I
would do this:

auto numLessThanN = numbers.indexed(order).countUntil!((x) => x
= N)();

```
Jun 11 2014
"Andrew Brown" <aabrown24 hotmail.com> writes:
``` My question about this is how lazy is map? Will it work on
every value of order and then pass it to lowerBound, or could
it work to evaluate only those values asked by lowerBound? I
guess probably not, but could a function be composed that
worked in this way?

Thank you very much

Andrew

map is fully lazy.

However, if you've already got the sorted indices in `order`, I
would do this:

auto numLessThanN = numbers.indexed(order).countUntil!((x) => x
= N)();

Thanks for the reply, I'm going to have a lot of numbers though.
I guess compared to the time it will take me to sort them, it
makes no difference, but is it right that countUntil will take
linear time? If I can figure out lowerBound, then I have my

Best

Andrew
```
Jun 11 2014
"John Colvin" <john.loughran.colvin gmail.com> writes:
```On Wednesday, 11 June 2014 at 11:38:07 UTC, Andrew Brown wrote:
every value of order and then pass it to lowerBound, or could
it work to evaluate only those values asked by lowerBound? I
guess probably not, but could a function be composed that
worked in this way?

Thank you very much

Andrew

map is fully lazy.

However, if you've already got the sorted indices in `order`,
I would do this:

auto numLessThanN = numbers.indexed(order).countUntil!((x) => x
= N)();

Thanks for the reply, I'm going to have a lot of numbers
though. I guess compared to the time it will take me to sort
them, it makes no difference, but is it right that countUntil
will take linear time? If I can figure out lowerBound, then I
have my answer in log(n) time?

Best

Andrew

You are correct. assumeSorted and lowerBound will provide better
time complexity than countUntil
```
Jun 11 2014
"Andrew Brown" <aabrown24 hotmail.com> writes:
``` You are correct. assumeSorted and lowerBound will provide
better time complexity than countUntil

I'm sorry, one final question because I think I'm close to
understanding. Map produces a forward range (lazily) but not a
random access range? Therefore, lowerBound will move along this
range until the pred is not true? This means it would be better
to do:

numbers.indexed(order).assumeSorted.lowerBound

than:

map(a => numbers[a])(order).assumeSorted.lowerBound

as the lowerBound will be faster on a random access range as
produced by indexed?
```
Jun 11 2014
"John Colvin" <john.loughran.colvin gmail.com> writes:
```On Wednesday, 11 June 2014 at 13:20:37 UTC, Andrew Brown wrote:
You are correct. assumeSorted and lowerBound will provide
better time complexity than countUntil

I'm sorry, one final question because I think I'm close to
understanding. Map produces a forward range (lazily) but not a
random access range? Therefore, lowerBound will move along this
range until the pred is not true? This means it would be better
to do:

numbers.indexed(order).assumeSorted.lowerBound

than:

map(a => numbers[a])(order).assumeSorted.lowerBound

as the lowerBound will be faster on a random access range as
produced by indexed?

map preserves the random access capabilities of it's source. An
array is random access, therefore map applied to an array is also
random access.

There isn't any practical difference between indices.map!((i) =>
src[i])() and src.indexed(indices) that I know of.
```
Jun 11 2014
"Andrew Brown" <aabrown24 hotmail.com> writes:
```On Wednesday, 11 June 2014 at 13:25:03 UTC, John Colvin wrote:
On Wednesday, 11 June 2014 at 13:20:37 UTC, Andrew Brown wrote:
You are correct. assumeSorted and lowerBound will provide
better time complexity than countUntil

I'm sorry, one final question because I think I'm close to
understanding. Map produces a forward range (lazily) but not a
random access range? Therefore, lowerBound will move along
this range until the pred is not true? This means it would be
better to do:

numbers.indexed(order).assumeSorted.lowerBound

than:

map(a => numbers[a])(order).assumeSorted.lowerBound

as the lowerBound will be faster on a random access range as
produced by indexed?

map preserves the random access capabilities of it's source. An
array is random access, therefore map applied to an array is
also random access.

There isn't any practical difference between indices.map!((i)
=> src[i])() and src.indexed(indices) that I know of.

That's great, thank you very much for taking the time to answer.
```
Jun 11 2014
"Andrew Brown" <aabrown24 hotmail.com> writes:
```So I was hoping for a learning experience, and I got it. With a
little playing around, looking at phobos, and TDPL, I think I've
figured out how lowerBound gets its predicate. It learns it from
assumeSorted. So I can do this:

order.assumeSorted!((a, b) => number[a] < number[b])
.lowerBound(order[4])

and I'll retrieve the indices of the 4 smallest numbers. Not
useful for my current purposes, but is getting me closer to
figuring out how higher level functions and ranges work.

Thanks

Andrew
```
Jun 11 2014
"Andrew Brown" <aabrown24 hotmail.com> writes:
``` map is fully lazy.

However, if you've already got the sorted indices in `order`, I
would do this:

auto numLessThanN = numbers.indexed(order).countUntil!((x) => x
= N)();

That indexed command is perfect though, does the trick, thank you
very much.
```
Jun 11 2014
"John Colvin" <john.loughran.colvin gmail.com> writes:
```On Wednesday, 11 June 2014 at 11:50:36 UTC, Andrew Brown wrote:
map is fully lazy.

However, if you've already got the sorted indices in `order`,
I would do this:

auto numLessThanN = numbers.indexed(order).countUntil!((x) => x
= N)();

That indexed command is perfect though, does the trick, thank
you very much.

For future reference: map applies its predicate in `front`,
meaning that

a) It is completely lazy, you only pay for elements you actually
access.

b) Unless the optimiser is smart and caches the result for you,
you pay every time you call `front`, even if you haven't called
`popFront` in between.
```
Jun 11 2014