views:

317

answers:

4

I'm guessing that there must be a better functional way of expressing the following:

def foo(i: Any) : Int

if (foo(a) < foo(b)) a else b 

So in this example f == foo and p == _ < _. There's bound to be some masterful cleverness in scalaz for this! I can see that using BooleanW I can write:

p(f(a), f(b)).option(a).getOrElse(b)

But I was sure that I would be able to write some code which only referred to a and b once. If this exists it must be on some combination of Function1W and something else but scalaz is a bit of a mystery to me!

EDIT: I guess what I'm asking here is not "how do I write this?" but "What is the correct name and signature for such a function and does it have anything to do with FP stuff I do not yet understand like Kleisli, Comonad etc?"

+3  A: 

Just in case it's not in Scalaz:

def x[T,R](f : T => R)(p : (R,R) => Boolean)(x : T*) =
  x reduceLeft ((l, r) => if(p(f(l),f(r))) r else l)

scala> x(Math.pow(_ : Int,2))(_ < _)(-2, 0, 1)
res0: Int = -2

Alternative with some overhead but nicer syntax.

class MappedExpression[T,R](i : (T,T), m : (R,R)) {
  def select(p : (R,R) => Boolean ) = if(p(m._1, m._2)) i._1 else i._2 
}

class Expression[T](i : (T,T)){
  def map[R](f: T => R) = new MappedExpression(i, (f(i._1), f(i._2)))
}

implicit def tupleTo[T](i : (T,T)) = new Expression(i)

scala> ("a", "bc") map (_.length) select (_ < _)
res0: java.lang.String = a
Thomas Jung
Yes - I realize I could write the function itself. I suppose I wanted to know what the "correct" name for this kind of thing was in FP. Is this to with the Kleisli whatsits? I have no idea!
oxbow_lakes
I've assumed that already but could not resist to write it anyway. Kleisli whatsits is just white noise for me.
Thomas Jung
Give `x` a descriptive name and I might even accept your answer!
oxbow_lakes
It may be better this way: `(a, b) map (f(_)) x (p(_,_))`.
Thomas Jung
@Thomas - but there's no way I can see that you could write x in such a way as to allow this syntax. How would that work?
oxbow_lakes
I added it as an alternative. There is still some room for improving the naming of the methods.
Thomas Jung
Ah - I thought you were saying this was possible with the original method definition. Awesome answer!
oxbow_lakes
Now you can define `("a", "bc") -> ( _.length) | (_ < _)`. Or some other even more cryptic version.
Thomas Jung
I went a long way starting from your type signature, through Haskell, and then got all the way back to your solution. Only, on the trip, your `map` got renamed to `on`.
Daniel
@Daniel +1 for map -> on and the anonymous classes.
Thomas Jung
@Thomas the combination of anonymous classes and implicits result in reflection, which makes the combination a bad choice most of the time. I only used it to keep the type signatures as close as possible to the original.
Daniel
+2  A: 

Well, I looked up Hoogle for a type signature like the one in Thomas Jung's answer, and there is on. This is what I searched for:

(a -> b) -> (b -> b -> Bool) -> a -> a -> a

Where (a -> b) is the equivalent of foo, (b -> b -> Bool) is the equivalent of <. Unfortunately, the signature for on returns something else:

(b -> b -> c) -> (a -> b) -> a -> a -> c

This is almost the same, if you replace c with Bool and a in the two places it appears, respectively.

So, right now, I suspect it doesn't exist. It occured to me that there's a more general type signature, so I tried it as well:

(a -> b) -> ([b] -> b) -> [a] -> a

This one yielded nothing.

EDIT:

Now I don't think I was that far at all. Consider, for instance, this:

Data.List.maximumBy (on compare length) ["abcd", "ab", "abc"]

The function maximumBy signature is (a -> a -> Ordering) -> [a] -> a, which, combined with on, is pretty close to what you originally specified, given that Ordering is has three values -- almost a boolean! :-)

So, say you wrote on in Scala:

def on[A, B, C](f: ((B, B) => C), g: A => B): (A, A) => C = (a: A, b: A) => f(g(a), g(b))

The you could write select like this:

def select[A](p: (A, A) => Boolean)(a: A, b: A) = if (p(a, b)) a else b

And use it like this:

select(on((_: Int) < (_: Int), (_: String).length))("a", "ab")

Which really works better with currying and dot-free notation. :-) But let's try it with implicits:

implicit def toFor[A, B](g: A => B) = new { 
  def For[C](f: (B, B) => C) = (a1: A, a2: A) => f(g(a1), g(a2)) 
}
implicit def toSelect[A](t: (A, A)) = new { 
  def select(p: (A, A) => Boolean) = t match { 
    case (a, b) => if (p(a, b)) a else b 
  } 
}

Then you can write

("a", "ab") select (((_: String).length) For (_ < _))

Very close. I haven't figured any way to remove the type qualifier from there, though I suspect it is possible. I mean, without going the way of Thomas answer. But maybe that is the way. In fact, I think on (_.length) select (_ < _) reads better than map (_.length) select (_ < _).

Daniel
There was a question about the 'on' function and Scala already. But I could not find it again. It's not exactly an easily searchable word.
Thomas Jung
I couldn't figure out how to compose `on` so that it had "access" to the original data. The issue being that this question is a "special case" for a predicate whereas `on` is more general
oxbow_lakes
@oxbow Both the `on` and the `For` -- which is nothing more than an inverted `on`, to take advantage of type inference -- are particular strict about the data types. Only `select` is bound to `Pair` and `Boolean`. What would be the more general case?
Daniel
+3  A: 

I don't think that Arrows or any other special type of computation can be useful here. Afterall, you're calculating with normal values and you can usually lift a pure computation that into the special type of computation (using arr for arrows or return for monads).

However, one very simple arrow is arr a b is simply a function a -> b. You could then use arrows to split your code into more primitive operations. However, there is probably no reason for doing that and it only makes your code more complicated.

You could for example lift the call to foo so that it is done separately from the comparison. Here is a simiple definition of arrows in F# - it declares *** and >>> arrow combinators and also arr for turning pure functions into arrows:

type Arr<'a, 'b> = Arr of ('a -> 'b)
let arr f = Arr f
let ( *** ) (Arr fa) (Arr fb) = Arr (fun (a, b) -> (fa a, fb b))
let ( >>> ) (Arr fa) (Arr fb) = Arr (fa >> fb)

Now you can write your code like this:

let calcFoo = arr <| fun a -> (a, foo a)    
let compareVals = arr <| fun ((a, fa), (b, fb)) -> if fa < fb then a else b

(calcFoo *** calcFoo) >>> compareVals

The *** combinator takes two inputs and runs the first and second specified function on the first, respectively second argument. >>> then composes this arrow with the one that does comparison.

But as I said - there is probably no reason at all for writing this.

Tomas Petricek
I understand almost nothing of this answer. +1
oxbow_lakes
+2  A: 

Here's the Arrow based solution, implemented with Scalaz. This requires trunk.

You don't get a huge win from using the arrow abstraction with plain old functions, but it is a good way to learn them before moving to Kleisli or Cokleisli arrows.

import scalaz._
import Scalaz._

def mod(n: Int)(x: Int) = x % n
def mod10 = mod(10) _
def first[A, B](pair: (A, B)): A = pair._1
def selectBy[A](p: (A, A))(f: (A, A) => Boolean): A = if (f.tupled(p)) p._1 else p._2
def selectByFirst[A, B](f: (A, A) => Boolean)(p: ((A, B), (A, B))): (A, B) =
  selectBy(p)(f comap first) // comap adapts the input to f with function first.

val pair = (7, 16)

// Using the Function1 arrow to apply two functions to a single value, resulting in a Tuple2
((mod10 &&& identity) apply 16) assert_≟ (6, 16)

// Using the Function1 arrow to perform mod10 and identity respectively on the first and second element of a `Tuple2`.
val pairs = ((mod10 &&& identity) product) apply pair
pairs assert_≟ ((7, 7), (6, 16))

// Select the tuple with the smaller value in the first element.
selectByFirst[Int, Int](_ < _)(pairs)._2 assert_≟ 16

// Using the Function1 Arrow Category to compose the calculation of mod10 with the
// selection of desired element.
val calc = ((mod10 &&& identity) product) ⋙ selectByFirst[Int, Int](_ < _)
calc(pair)._2 assert_≟ 16
retronym