Плохо, что в Скале оптимизация хвостовых вызовов не делается, кроме как для прямой рекурсии. Т.е., взаимная рекурсия в таком варианте уже не прокатит, придется использовать костыль trampoline. А это накладные расходы, и уже не такой ясный код.
Исходный код
def countWords(s: String) = { def space(n: Int, xs: List[Char]): Int = xs match { case Nil => n case ' ' :: xs => space(n, xs) case x :: xs => word(n + 1, xs) } def word(n: Int, xs: List[Char]): Int = xs match { case Nil => n case ' ' :: xs => space(n, xs) case x :: xs => word(n, xs) } space(0, s.toList) }
Прочитал первые две прочитанных в МИФИ лекций по ФП (то что Яндекс первым выплюнул). Впечатления: 1. Понравилось - ново, головоломно и кратко 2. Сильно непривычно 3. Синтаксис Haskell в этой теме на первых страницах невозможно понять без базового разбора синтаксиса ФП
Если пишешь под .net, то погляди в сторону Nemerle (http://ru.wikipedia.org/wiki/Nemerle). В отличии от f# имеет синтаксис, похожий на шарп, это эдакий си-шарп-на-стероидах. Органично (насколько это можно) объединяет парадигмы объектно-ориентированного, функционального и мета-программирования.
На rsdn-е есть цикл статей, посвященных языку - http://rsdn.ru/?summary/3766.xml . Пишет статьи российский разработчик - один из членов команды разарабочиков nemerle. На rsdn-е же расположен русскоязычный форум поддержки.
Сообщение отредактировал SeregaA - Jul 8 2010, 16:47
Возвращаясь к вопросу о якобы слабой системе типов Скалы в сравнении с системой типов Хаскелл, который поднимался не так давно в Курилке, хочу ввести исчисление на типах Скалы. Или система типов как формальная система, или комбинаторная логика на типах.
Итак, дамы и господа, представляю вашему вниманию общий интерфейс для термов (типов), т.е, переменных, комбинаторов, и их комбинаций, а также два комбинатора S (коннектор) и K (канцелятор), образующих минимальный базис (один из множества возможных):
Исходный код
scala> trait Term { | type App[A <: Term] <: Term | type Eval <: Term | } defined trait Term
scala> trait K2[A <: Term, B <: Term] extends Term { | type App[C <: Term] = Eval#App[C] | type Eval = A#Eval | } defined trait K2
scala> trait K1[A <: Term] extends Term { | type App[B <: Term] = K2[A, B] | type Eval = K1[A] | } defined trait K1
scala> trait K extends Term { | type App[A <: Term] = K1[A] | type Eval = K | } defined trait K
scala> trait S3[A <: Term, B <: Term, C <: Term] extends Term { | type App[D <: Term] = Eval#App[D] | type Eval = A#App[C]#App[B#App[C]]#Eval | } defined trait S3
scala> trait S2[A <: Term, B <: Term] extends Term { | type App[C <: Term] = S3[A, B, C] | type Eval = S2[A, B] | } defined trait S2
scala> trait S1[A <: Term] extends Term { | type App[B <: Term] = S2[A, B] | type Eval = S1[A] | } defined trait S1
scala> trait S extends Term { | type App[A <: Term] = S1[A] | type Eval = S | } defined trait S
А это определение класса, используемого для доказательства эквивалентности двух термов. В случае равенства сравниваемых термов инстанцируется экземпляр класса Eq, иначе вызывается ошибка компиляции. Здесь же определяется пара вспомогательных переменных X и Y:
Исходный код
scala> class Eq[A >: B <: B, B] defined class Eq
scala> new Eq[Int, Int] res0: Eq[Int,Int] = Eq@1c6cc9c
scala> new Eq[Int, Double] <console>:6: error: type arguments [Int,Double] do not conform to class Eq's type parameter bounds [A >: B <: B,B] val res1 = ^ <console>:7: error: type arguments [Int,Double] do not conform to class Eq's type parameter bounds [A >: B <: B,B] new Eq[Int, Double] ^
scala> trait X extends Term { | type App[A <: Term] = X | type Eval = X | } defined trait X
scala> trait Y extends Term { | type App[A <: Term] = Y | type Eval = Y | } defined trait Y
Нужно убедиться в том, что введенные комбинаторы ведут себя так, как задумано:
Исходный код
scala> new Eq[K#App[X]#App[Y]#Eval, X] // Kxy = x res2: Eq[X,X] = Eq@93fd01
scala> new Eq[S#App[K]#App[K]#App[X]#Eval, X] // SKKx = x res3: Eq[X,X] = Eq@1450337
Все ОК.
Теперь на основе базисных комбинаторов можно получить остальные. Например, вот так определяются композитор, пермутатор, комбинатор тождества и дубликатор:
Исходный код
scala> type B = S#App[K#App[S]]#App[K] // S(KS)K, Bxyz = x(yz) defined type alias B
scala> type C = S#App[B#App[B]#App[S]]#App[K#App[K]] // S(BBS)(KK), Cxyz = xzy defined type alias C
scala> type I = S#App[K]#App[K] // SKK, Ix = x defined type alias I
scala> type W = S#App[S]#App[K#App[I]] // SS(KI), Wxy = xyy defined type alias W
Продолжу. Комбинаторная логика как инструмент кодирования объектов и операций над ними. Пример первый, упорядоченная пара, а также ее первая и вторая проекции:
Исходный код
scala> type Pair = B#App[C]#App[C#App[I]] // BC(CI) defined type alias Pair
scala> type Fst = C#App[I]#App[K] // CIK defined type alias Fst
scala> type Snd = C#App[I]#App[K#App[I]] // CI(KI) defined type alias Snd
Нужно убедиться, что этот код компилируется:
Исходный код
scala> new Eq[Fst#App[Pair#App[X]#App[Y]]#Eval, X] res4: Eq[X,X] = Eq@15b44d6
scala> new Eq[Snd#App[Pair#App[X]#App[Y]]#Eval, Y] res5: Eq[Y,Y] = Eq@a05bc3
А этот нет:
Исходный код
scala> new Eq[Fst#App[Pair#App[X]#App[Y]]#Eval, Y] <console>:21: error: type arguments [X,Y] do not conform to class Eq's type parameter bounds [A >: B <: B,B] val res6 = ^ <console>:22: error: type arguments [X,Y] do not conform to class Eq's type parameter bounds [A >: B <: B,B] new Eq[Fst#App[Pair#App[X]#App[Y]]#Eval, Y] ^
scala> new Eq[Snd#App[Pair#App[X]#App[Y]]#Eval, X] <console>:21: error: type arguments [Y,X] do not conform to class Eq's type parameter bounds [A >: B <: B,B] val res7 = ^ <console>:22: error: type arguments [Y,X] do not conform to class Eq's type parameter bounds [A >: B <: B,B] new Eq[Snd#App[Pair#App[X]#App[Y]]#Eval, X] ^
Пример следующий, булевы значения и несколько операций над ними, или алгебра логики:
Исходный код
scala> type T = K // True defined type alias T
scala> type F = K#App[I] // False defined type alias F
scala> type If = I defined type alias If
scala> type Or = S#App[I]#App[K#App[K]] // SI(KK) defined type alias Or
scala> type And = S#App[S]#App[K#App[K#App[K#App[I]]]] // SS(K(K(KI))) defined type alias And
scala> type Not = S#App[S#App[I]#App[K#App[K#App[I]]]]#App[K#App[K]] // S(SI(K(KI)))(KK) defined type alias Not
И опять необходимая проверка. Этот код рабочий:
Исходный код
scala> new Eq[If#App[T]#App[X]#App[Y]#Eval, X] res8: Eq[X,X] = Eq@150818a
scala> new Eq[If#App[F]#App[X]#App[Y]#Eval, Y] res9: Eq[Y,Y] = Eq@1ef48fb
scala> new Eq[Or#App[T]#App[T]#Eval, T] res10: Eq[K,T] = Eq@1949a87
scala> new Eq[Or#App[T]#App[F]#Eval, T] res11: Eq[K,T] = Eq@c98b07
scala> new Eq[Or#App[F]#App[T]#Eval, T] res12: Eq[K,T] = Eq@11067af
scala> new Eq[Or#App[F]#App[F]#Eval, F] res13: Eq[K1[S2[K,K]],F] = Eq@18efa2f
scala> new Eq[And#App[T]#App[T]#Eval, T] res14: Eq[K,T] = Eq@f186b8
scala> new Eq[And#App[T]#App[F]#Eval, F] res15: Eq[K1[S2[K,K]],F] = Eq@15f0876
scala> new Eq[And#App[F]#App[T]#Eval, F] res16: Eq[K1[S2[K,K]],F] = Eq@1df471
scala> new Eq[And#App[F]#App[F]#Eval, F] res17: Eq[K1[S2[K,K]],F] = Eq@39aca7
scala> new Eq[Not#App[T]#Eval, F] res18: Eq[K1[S2[K,K]],F] = Eq@84850
scala> new Eq[Not#App[F]#Eval, T] res19: Eq[K,T] = Eq@7227a8
А этот нет:
Исходный код
scala> new Eq[If#App[T]#App[X]#App[Y]#Eval, Y] <console>:19: error: type arguments [X,Y] do not conform to class Eq's type parameter bounds [A >: B <: B,B] val res20 = ^ <console>:20: error: type arguments [X,Y] do not conform to class Eq's type parameter bounds [A >: B <: B,B] new Eq[If#App[T]#App[X]#App[Y]#Eval, Y] ^
scala> new Eq[If#App[F]#App[X]#App[Y]#Eval, X] <console>:19: error: type arguments [Y,X] do not conform to class Eq's type parameter bounds [A >: B <: B,B] val res21 = ^ <console>:20: error: type arguments [Y,X] do not conform to class Eq's type parameter bounds [A >: B <: B,B] new Eq[If#App[F]#App[X]#App[Y]#Eval, X] ^
scala> new Eq[Or#App[T]#App[T]#Eval, F] <console>:18: error: type arguments [K,F] do not conform to class Eq's type parameter bounds [A >: B <: B,B] val res22 = ^ <console>:19: error: type arguments [K,F] do not conform to class Eq's type parameter bounds [A >: B <: B,B] new Eq[Or#App[T]#App[T]#Eval, F] ^
scala> new Eq[Or#App[T]#App[F]#Eval, F] <console>:18: error: type arguments [K,F] do not conform to class Eq's type parameter bounds [A >: B <: B,B] val res23 = ^ <console>:19: error: type arguments [K,F] do not conform to class Eq's type parameter bounds [A >: B <: B,B] new Eq[Or#App[T]#App[F]#Eval, F] ^
scala> new Eq[Or#App[F]#App[T]#Eval, F] <console>:18: error: type arguments [K,F] do not conform to class Eq's type parameter bounds [A >: B <: B,B] val res24 = ^ <console>:19: error: type arguments [K,F] do not conform to class Eq's type parameter bounds [A >: B <: B,B] new Eq[Or#App[F]#App[T]#Eval, F] ^
scala> new Eq[Or#App[F]#App[F]#Eval, T] <console>:18: error: type arguments [K1[S2[K,K]],T] do not conform to class Eq's type parameter bounds [A >: B <: B,B] val res25 = ^ <console>:19: error: type arguments [K1[S2[K,K]],T] do not conform to class Eq's type parameter bounds [A >: B <: B,B] new Eq[Or#App[F]#App[F]#Eval, T] ^
scala> new Eq[And#App[T]#App[T]#Eval, F] <console>:18: error: type arguments [K,F] do not conform to class Eq's type parameter bounds [A >: B <: B,B] val res26 = ^ <console>:19: error: type arguments [K,F] do not conform to class Eq's type parameter bounds [A >: B <: B,B] new Eq[And#App[T]#App[T]#Eval, F] ^
scala> new Eq[And#App[T]#App[F]#Eval, T] <console>:18: error: type arguments [K1[S2[K,K]],T] do not conform to class Eq's type parameter bounds [A >: B <: B,B] val res27 = ^ <console>:19: error: type arguments [K1[S2[K,K]],T] do not conform to class Eq's type parameter bounds [A >: B <: B,B] new Eq[And#App[T]#App[F]#Eval, T] ^
scala> new Eq[And#App[F]#App[T]#Eval, T] <console>:18: error: type arguments [K1[S2[K,K]],T] do not conform to class Eq's type parameter bounds [A >: B <: B,B] val res28 = ^ <console>:19: error: type arguments [K1[S2[K,K]],T] do not conform to class Eq's type parameter bounds [A >: B <: B,B] new Eq[And#App[F]#App[T]#Eval, T] ^
scala> new Eq[And#App[F]#App[F]#Eval, T] <console>:18: error: type arguments [K1[S2[K,K]],T] do not conform to class Eq's type parameter bounds [A >: B <: B,B] val res29 = ^ <console>:19: error: type arguments [K1[S2[K,K]],T] do not conform to class Eq's type parameter bounds [A >: B <: B,B] new Eq[And#App[F]#App[F]#Eval, T] ^
scala> new Eq[Not#App[T]#Eval, T] <console>:17: error: type arguments [K1[S2[K,K]],T] do not conform to class Eq's type parameter bounds [A >: B <: B,B] val res30 = ^ <console>:18: error: type arguments [K1[S2[K,K]],T] do not conform to class Eq's type parameter bounds [A >: B <: B,B] new Eq[Not#App[T]#Eval, T] ^
scala> new Eq[Not#App[F]#Eval, F] <console>:17: error: type arguments [K,F] do not conform to class Eq's type parameter bounds [A >: B <: B,B] val res31 = ^ <console>:18: error: type arguments [K,F] do not conform to class Eq's type parameter bounds [A >: B <: B,B] new Eq[Not#App[F]#Eval, F] ^
Еще бы не помешало рассмотреть нумералы Черча, но с ними у меня случилась неприятность. Проблема, как я понимаю, связана с частичной аппликацией, но вроде бы есть способ ее обойти, используя одно свойство нумералов. Если получится, то кину сюда, конечно, при условии, что никто не будет возражать
Кое-что получилось. Вот нумералы Чёрча и операции следования, сложения, умножения и возведения в степень:
Исходный код
scala> type Succ = S#App[B] // SB defined type alias Succ
scala> type Add = C#App[I]#App[S#App[B]] // CI(SB) defined type alias Add
scala> type Mul = B defined type alias Mul
scala> type Exp = C#App[I] // CI defined type alias Exp
scala> type _0 = K#App[I] // KI defined type alias _0
scala> type _1 = Succ#App[_0] // SB(KI) defined type alias _1
scala> type _2 = Succ#App[Succ#App[_0]] // SB(SB(KI)) defined type alias _2
scala> type _3 = Succ#App[Succ#App[Succ#App[_0]]] // SB(SB(SB(KI))) defined type alias _3
scala> type _4 = Succ#App[Succ#App[Succ#App[Succ#App[_0]]]] // SB(SB(SB(SB(KI)))) defined type alias _4
Для проверки закодированных таким образом чисел можно воспользоваться тем фактом, что используемый вариант нумералов по сути является разверткой или анаморфизмом, если говорить категорным языком. Т.е., числа возможно преобразовать в изоморфную им структуру, например, список. Для этого определю вспомогательную функцию-тип Unfold, а также список L:
Исходный код
scala> trait L1[K <: Term] extends Term { | type App[M <: Term] = L1[M] | type Eval = L1[K#Eval] | } defined trait L1
scala> trait L extends Term { | type App[K <: Term] = L1[K] | type Eval = L | } defined trait L
scala> type Unfold[N <: Term] = N#App[L]#App[L] defined type alias Unfold
И опять нужно убедиться, что все верно:
Исходный код
scala> new Eq[Unfold[_0]#Eval, L] res16: Eq[L,L] = Eq@105c7e1
scala> new Eq[Unfold[_1]#Eval, L#App[L]] res17: Eq[L1[L],L1[L]] = Eq@d593f7
scala> new Eq[Unfold[_2]#Eval, L#App[L#App[L]]] res18: Eq[L1[L1[L]],L1[L1[L]]] = Eq@1eb41d6
scala> new Eq[Unfold[_3]#Eval, L#App[L#App[L#App[L]]]] res19: Eq[L1[L1[L1[L]]],L1[L1[L1[L]]]] = Eq@112ee4f
scala> new Eq[Unfold[_4]#Eval, L#App[L#App[L#App[L#App[L]]]]] res20: Eq[L1[L1[L1[L1[L]]]],L1[L1[L1[L1[L]]]]] = Eq@b56559
scala> new Eq[Unfold[Add#App[_1]#App[_0]]#Eval, Unfold[_1]#Eval] res21: Eq[L1[L],L1[L]] = Eq@1415dbf
scala> new Eq[Unfold[Add#App[_0]#App[_1]]#Eval, Unfold[_1]#Eval] res22: Eq[L1[L],L1[L]] = Eq@fe8c4
scala> new Eq[Unfold[Add#App[_2]#App[_2]]#Eval, Unfold[_4]#Eval] res23: Eq[L1[L1[L1[L1[L]]]],L1[L1[L1[L1[L]]]]] = Eq@a7bdcd
scala> new Eq[Unfold[Add#App[_1]#App[_3]]#Eval, Unfold[_4]#Eval] res24: Eq[L1[L1[L1[L1[L]]]],L1[L1[L1[L1[L]]]]] = Eq@1b8cdd5
scala> new Eq[Unfold[Mul#App[_0]#App[_0]]#Eval, Unfold[_0]#Eval] res25: Eq[L,L] = Eq@120e750
scala> new Eq[Unfold[Mul#App[_0]#App[_4]]#Eval, Unfold[_0]#Eval] res26: Eq[L,L] = Eq@10a7be0
scala> new Eq[Unfold[Mul#App[_1]#App[_1]]#Eval, Unfold[_1]#Eval] res27: Eq[L1[L],L1[L]] = Eq@1b7a531
scala> new Eq[Unfold[Mul#App[_2]#App[_2]]#Eval, Unfold[_4]#Eval] res28: Eq[L1[L1[L1[L1[L]]]],L1[L1[L1[L1[L]]]]] = Eq@1e3d24a
scala> new Eq[Unfold[Exp#App[_0]#App[_0]]#Eval, Unfold[_1]#Eval] res29: Eq[L1[L],L1[L]] = Eq@a4ceeb
scala> new Eq[Unfold[Exp#App[_2]#App[_1]]#Eval, Unfold[_2]#Eval] res30: Eq[L1[L1[L]],L1[L1[L]]] = Eq@b6be69
scala> new Eq[Unfold[Exp#App[_2]#App[_2]]#Eval, Unfold[_4]#Eval] res31: Eq[L1[L1[L1[L1[L]]]],L1[L1[L1[L1[L]]]]] = Eq@1c55e69
Чуть-чуть оживлю что ли тему, так сказать, разбавлю скучную обстановку. Мне интересно было наваять что-нибудь такое из функционального мира в мире ОО, пока в отпуске делать нечего Вот что получилось на скорую руку. Начну с простенького, лямбда функции:
Исходный код
interface Function1<A, B> { B apply(A a); }
class Lambda { public static void main(String[] args) { Function1<Integer, Integer> square = new Function1<Integer, Integer>() { public Integer apply(Integer x) { return x * x; } }; System.out.println(square.apply(2)); } }