Using type classes indexed by the singleton types of function values to statically verify interesting properties. Obviously this relies on the instance declaration telling the truth but, given that, it is nevertheless checkable at use sites.

gistfile1.scala

scala> trait Pure[T]
defined trait Pure

scala> val plusOne: Int => Int = _ + 1
plusOne: Int => Int = <function1>

scala> val frobPlusOne: Int => Int = { i => println("frob") ; i + 1 }
frobPlusOne: Int => Int = <function1>

scala> implicit val plusOneIsPure = new Pure[plusOne.type]{}
plusOneIsPure: Pure[plusOne.type] = $anon$1@20b8610d

scala> def map[A, B](l: List[A], f: A => B)(implicit fIsPure: Pure[f.type]) = l map f
map: [A, B](l: List[A], f: A => B)(implicit fIsPure: Pure[f.type])List[B]

scala> map(List(1, 2, 3), plusOne)
res0: List[Int] = List(2, 3, 4)

scala> map(List(1, 2, 3), frobPlusOne)
<console>:13: error: could not find implicit value for parameter fIsPure: Pure[frobPlusOne.type]
              map(List(1, 2, 3), frobPlusOne)