• Post Reply Bookmark Topic Watch Topic
  • New Topic

Compute the difference between successive elements of vector using functional programming  RSS feed

 
Mark Bower
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Have searched everywhere for an answer to this, but as soon as I type the "diff" and "functional", all I get are responses about the difference between functional and declarative programming. What I want is a functional equivalent of a Matlab "diff" function: namely, the difference between successive elements of a vector. For example, if:
the input is a vector "1 2 5 7 9",
the desired result has "1 3 2 2"
where I have used weird wording to get the result elements to line up between input elements to emphasize how the result is obtained. Another way to say this is "For vector v, result = [ v(2)-v(1)   v(3)-v(2)   v(4)-v(3) ...]. Another way to say it is that I want a functional way to compute the first derivative of a vector.

Best I can figure, you need some type of "map" function, but the tricky part is that the result will always contain one less element than the input. In declarative languages, this is easy; you just loop through the elements and make sure that your result is stored in the proper locations: input(2)-input(1) goes into result(1) and so on. I've read three "functional programming" books, but they seem overly fascinated with GUI applications and spend little time on computation

Any help would be appreciated, particularly books/tutorial on scientific computing using functional programming.
 
Piet Souris
Rancher
Posts: 1783
55
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Were this Scala, I would simply use: list1 zip list1.tail map (e => e._2 - e._1). For instance:

In Java, you can do the same thing with the use of a Stream, albeit that we do not have a 'zip' and a 'tail' method, Now, it is easy to make one, and you would likewise get:
zip(list1, list2).stream().map(...)

And you can also do the somewhat ugly IntStream.iterate(0, list.size)....

Choices in abundance. The real specialists around here (like Jesper and Stephan) probably can show you how to incorporate a zip method in a stream, so that you don't need a separate zip function.

Anyway, I've noticed that often a simple classical for-loop does the job much much easier...
 
Pierre-Yves Saumont
Author
Ranch Hand
Posts: 98
17
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Instead of writing a zip method, you can fold the list using a Tuple<Integer, List<Integer>> as the accumulator :



Of course, you could write a specific tuple class instead of a parameterized one, but if you are going to do much FP in Java, you will need a parameterized Tuple class. Note that I wrote cons and tail methods because adding and dropping elements to/from lists are not functions in Java. But as for Tuple, you will probably need a more "functional" List class.

Also note that I have not included error handling. The tail method should return an Optional which would be empty if the list is empty. And of course, the tail and cons method should make a copy of their argument and modify and return this copy. As they are written, they have the side effect of mutating their argument, so they are not functional at all!

For more information, you may refer to my book Functional Programming in Java
 
Piet Souris
Rancher
Posts: 1783
55
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Seems like I forgot to mention at least one other specialist... 
 
Junilu Lacar
Sheriff
Posts: 10880
158
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This worked for me:

Could the caveat with this solution be that it might give incorrect results if there is parallelism involved? This is the part of the API documentation for Stream.reduce() that makes me wonder: "but is not constrained to execute sequentially". This code relies on sequential execution for correctness.  I'm having trouble wrapping my head around PYS' line 8-9, although I appreciate that he noted the non-functional nature of his cons and tail methods, which I was about to point out before I read the rest of his post.
 
Junilu Lacar
Sheriff
Posts: 10880
158
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@Mark - and Welcome to the Ranch!

This wouldn't be for school homework, would it? We try not to abet plagiarism here by providing outright solutions but since there already was one provided previously, I decided to post what worked for me. Hopefully this will give you some helpful ideas but at the same time I hope you don't pass these off as your own if it's for schoolwork.
 
Pierre-Yves Saumont
Author
Ranch Hand
Posts: 98
17
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Junilu Lacar wrote:
Could the caveat with this solution be that it might give incorrect results if there is parallelism involved?
...
I'm having trouble wrapping my head around PYS' line 8-9, although I appreciate that he noted the non-functional nature of his cons and tail methods, which I was about to point out before I read the rest of his post.


My example will not work with parallelism neither because the combiner is a dummy one:



A combiner is mandatory with the reduce method (at least the version I used), but it makes no sense since the operation cannot be automatically parallelized. So I provided a dummy combiner. This is a prolbem with Stream, because you have to deal with automatic paralleization even if you don't wan't it.

Regarding lines 8-9, it might be easier to understand when broken on several lines, since it makes the types explicit:


 
Mark Bower
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you, all! Not only has this solved my problem, but it has helped me onward in my struggles to "shift my paradigm" and learn functional programming (FP).

Junilu Lacar wrote:@Mark - and Welcome to the Ranch!

This wouldn't be for school homework, would it? We try not to abet plagiarism here by providing outright solutions but since there already was one provided previously, I decided to post what worked for me. Hopefully this will give you some helpful ideas but at the same time I hope you don't pass these off as your own if it's for schoolwork.


Alas, I am a few decades past schoolwork! Since you asked, my application is biomedical signal processing. Terabytes of data that are well suited for parallel computation. I have only recently been introduced to FP, and for all of its benefits, I have been surprised at how little is written for FP and scientific computation (linear algebra, spectral analysis, etc.). Given that at least one author (Pierre - very nice book - enjoyed reading it!) responded, I will offer a suggestion that a market exists for a book on functional programming for scientific computing. The last well-known book I can think of along those lines was the Numerical Recipes series from the 80s, that many scientists still use to this day. I can think of a few books about Java for data analysis, but none have shown enough benefit to scientists to become popular. There would appear to be several benefits of FP in science, particularly in my own field (electrophysiology) where old, slow, non-scalable "languages" like Matlab still dominate. I would be happy to advise or collaborate, if anyone is interested. If someone would like to "talk offline", I would be happy to do so, if you let me know how to do that.

Thanks, again!

 
Otto Zeimer
Greenhorn
Posts: 16
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
one more solution with streams:
 
Junilu Lacar
Sheriff
Posts: 10880
158
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Mark Bower wrote:Alas, I am a few decades past schoolwork!

Good to know. Thanks for the clarification.

The approach I used is actually not recommended in the Java Tutorials: https://docs.oracle.com/javase/tutorial/collections/streams/parallelism.html because of the use of serial storage.

Here's another version I just played around with that appears to give the same results. I also tried putting .parallel() at different points in the chain and kept getting the correct results all the same. I don't know if doing that makes a difference (pun intended) though.

 
Junilu Lacar
Sheriff
Posts: 10880
158
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Even simpler still:

Again, I tried putting .parallel() at different points in the chain. TBH, I really don't know if doing that has any significance or relevance to the impact of parallelism.
 
Junilu Lacar
Sheriff
Posts: 10880
158
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Otto Zeimer wrote:one more solution with streams:

The trouble with this is that you can't extract it to a method that returns a list unless you use serial storage, as I did in my first proposed solution. You have to use serial storage to collect the results because max() is a terminal operation. I already pointed out that the practice of using serial storage is discouraged. Also, if you want to parallelize, this won't work, same as with some of the first solutions offered.
 
Stephan van Hulst
Saloon Keeper
Posts: 6989
110
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Pierre-Yves' solution violates the reduce() contract because his accumulator is not stateless. The same goes for Junilu's first solution.

I don't like Junilu's final solution because its time complexity depends on the type of list being used. It will be a lot slower for large sequential lists.

If I was forced to use a functional solution to this problem, I would use a mutable reduction:


This solution handles a parallel stream quickly and correctly. I could make this solution use the reduce() operation instead by making Diff immutable and making the addValue() and combine() methods return a new Diff, but that would be pointless and much slower.
 
Pierre-Yves Saumont
Author
Ranch Hand
Posts: 98
17
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:Pierre's solution violates the reduce() contract because his accumulator is not stateless.


As I said, I used a mutable list to simplify  the code. The good solution would be to use an immutable list, as I show in my book, but it would be to long to expose here. Anyway, in the solution I proposed, state mutation is not used. You may prefer:


 
Stephan van Hulst
Saloon Keeper
Posts: 6989
110
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes, that would work. You can make that solution work with parallel streams by using a Triple instead of a 2-Tuple, which includes the first value of a subsequence, and by changing your combiner to properly merge two triples.

I don't want to come across as rude, but I think this is a prime demonstration for why the Java developers chose not to add any tuple classes to the standard API. Creating a custom type for the specific problem makes the code much more readable than using a generic Triple type:


The latter has the added benefit of bundling behavior with the data, so you don't have to write long cryptic lambdas, but instead you can just call methods with clear names, or even just use a method handle. Your statement then becomes:

Which can be further simplified to


Admittedly, your code looks a lot more like what I would expect from classic functional languages like Haskell, but I don't think it's good to use Java to write Haskell.
 
Pierre-Yves Saumont
Author
Ranch Hand
Posts: 98
17
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It's all about requirements (and how we interpret them). In my understanding, the question was about how to write a functional implementation in Java. If the requirements wereto write a tool in Java to be used "functionally", I would write an imperative implementation of the diff function. If the requirements were not to write the implementation in Java, but only a tool to be used in Java, I would write the implementation in Scala. And if the requirements were not about Java at all, I would probably use Haskell.
 
Stephan van Hulst
Saloon Keeper
Posts: 6989
110
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Good point, I agree.
 
Piet Souris
Rancher
Posts: 1783
55
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hmm, why doing it simple if we can make it complex, I wonder.

I don't want to wake up old topics, but:

for me, the most interesting aspect is the requirement (as mentioned in the Stream-reduce API): the requirement of associativity. Do we have proven in all cases that:

f((f(a,b), c) = f(a, f(b, c))?  What does that mean in case of side effects?
 
Stephan van Hulst
Saloon Keeper
Posts: 6989
110
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
For Diffs a', b', and c', consider ab = f(a',b') and bc = f(b',c'), where f = combine.

a'.firstValue  = a
a'.lastValue   = a
a'.differences = []

b'.firstValue  = b
b'.lastValue   = b
b'.differences = []

c'.firstValue  = c
c'.lastValue   = c
c'.differences = []

ab.firstValue  = a
ab.lastValue   = b
ab.differences = [b-a]

bc.firstValue  = b
bc.lastValue   = c
bc.differences = [c-b]

Now consider abc1 = f(ab,c') and abc2 = f(a',bc).

abc1.firstValue  = a
abc1.lastValue   = c
abc1.differences = [b-a, c-b]

abc2.firstValue  = a
abc2.lastValue   = c
abc2.differences = [b-a, c-b]

This only provides the first steps of a complete proof of induction, but it should give you a feeling that the combine function is indeed associative.
 
Stephan van Hulst
Saloon Keeper
Posts: 6989
110
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Piet Souris wrote:What does that mean in case of side effects?

What side effects?
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!