Теория категорий, Haskell и программирование вообще

[warlock66613]

alex55555 в сообщении #1377694 писал(а):

Здесь вы как-то по своему определяете понятие ленивости.

Отнюдь. Я вообще ничего не определяю. Я только констатирую, что ленивость - по крайней мере ленивость Хаскелла - обладает определённым свойством.

alex55555 в сообщении #1377694 писал(а):

А вообще какое определение является "истинным" не знает никто

Но кроме вас я пока не встречал человека, которому бы это определение вообще было бы зачем-то нужно. Все и так понимают, что такое ленивость и зачем она нужна и что делает.

alex55555 в сообщении #1377694 писал(а):

Где-то должны быть эффекты.

И вновь - где эффеты и где seq. seq - это не про эффекты, это про оптимизацию.

[alex55555]

warlock66613 в сообщении #1377702 писал(а):

Но кроме вас я пока не встречал человека, которому бы это определение вообще было бы зачем-то нужно. Все и так понимают, что такое ленивость и зачем она нужна и что делает.

Когда "все и так понимают" наступают тёмные века.

warlock66613 в сообщении #1377702 писал(а):

alex55555 в сообщении #1377694 писал(а):

Где-то должны быть эффекты.

И вновь - где эффеты и где seq. seq - это не про эффекты, это про оптимизацию.

Как вам такой эффект - кончилась память?

[warlock66613]

alex55555 в сообщении #1377712 писал(а):

Как вам такой эффект - кончилась память?

Никак.

[Legioner93]

Anton_Peplov в сообщении #1377032 писал(а):

В теоркате я знаю только азы (первые главы выложенного здесь учебника), а программирую только на C#. С этим небольшим бэкграундом моя рабочая гипотеза состоит в том, что теоркат для программирования не нужен.

ТК нужна для нормального понимания заимствованных оттуда абстракций. Но ими можно и не пользоваться.

Anton_Peplov в сообщении #1377032 писал(а):

Впрочем, я вообще не знаю, какие области математики полезны для программирования как такового.

Обычно эти области объединяются под названием Computer Science. Кстати, так же называется и этот подфорум

-- Пт фев 22, 2019 19:34:48 --

warlock66613 в сообщении #1377602 писал(а):

Ленивость с точки зрения семантики языка сводится к возможности создания самоссылающихся объектов и других объектов бесконечной вложенности

Вы что имеете в виду? Бесконечное дерево можно создать почти в любом языке.

[Munin]

Legioner93 в сообщении #1377760 писал(а):

Бесконечное дерево можно создать почти в любом языке.

Можно пример на Pascal?

[Legioner93]

В паскале нельзя, ибо указатели. Но таких языков мало

[_Ivana]

Munin в сообщении #1377776 писал(а):

Можно пример на Pascal?

На Питоне/Джаваскрипте подойдет? Можно и на Си/Паскале разумеется, но лениво возиться с ручным управлением памятью и костылить лямбды/замыкания через структуры с указателем на функцию и аргументы. Принципиальных препятствий там тоже нет.
гист на Питоне
гист на Джаваскрипте

ЗЫ для не сильно категорных категоричных абстрактных участников рискну дать ссылку на мой недавний стрим на ютубе - про ежиков для юных сурков Просьба не предъявлять претензии по поводу не строгости и не академичности изложения - целевая аудитория была в основном из проходящих обучающие курсы по всяким Джаваскриптам.

alex55555 в сообщении #1377694 писал(а):

А вообще какое определение является "истинным" не знает никто

Нормальная и аппликативная стратегии редукции лямбда-термов вводятся чуть ли не с первых страниц любого букваря. Приоритетный левый внешний редекс или левый внутренний редекс, и т.п. Теоремка даже на этот счет есть - что если терм достиг нормальных форм по нормальной и по аппликативной стратегиям, то эти формы совпадают с точностью до альфа-конверсии. В Хаскеле смешанная стратегия колл бай нид - до вик хэд нормал форм, если аргументы конструктора типа не помечены как строгие, о чем уже неоднократно писали выше. Сколько можно писать простыни глупостей ученому соседу?

[Munin]

_Ivana в сообщении #1377870 писал(а):

На Питоне/Джаваскрипте подойдет?

Нет, это языки с принципиально другой семантикой. Подойдёт на Java или C#. Если очень хочется, на Fortran.

[_Ivana]

Ох и занудная эта ваша Джава... На скорую руку, но с мемоизацией:

Используется синтаксис Java

import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.concurrent.Callable;

class Cons {
    Object car;
    Object cdr;
    Cons(Object x, Object y) {this.car=x; this.cdr=y;}
}

class Memo {
    Callable expr;
    boolean calculated;
    Object rezult;
    Memo(Callable e) {this.expr=e; this.calculated=false;}
    Object getvalue() {
      if (!this.calculated) {
        try {
          this.rezult = this.expr.call();
          this.expr = null;
        } catch (Throwable ex) {
            // throw new RuntimeException("хрень");
        }
      }
      return this.rezult;
    }
}

class Main {
    
    public static Cons cons(Object x, Object y) {return new Cons(x, y);}

    public static Memo memo(Callable e) {return new Memo(e);}

    public static Cons stail(Cons s) {
        Object t = s.cdr;
        if (t instanceof Memo) {
          Memo c = (Memo) t;
          return (Cons) c.getvalue();
        } else return (Cons) t;
    }

    public static ArrayList stake (int n, Cons s) {
      ArrayList r = new ArrayList();
      while (n>0) {
        r.add(s.car);
        s = stail(s);
        n = n-1;}
      return r;
    }

    public static Cons ones = cons(1L, memo(new Callable<Cons>() {public Cons call() throws Exception {
        return ones;  
    }}));
      
    public static Cons intfrom(long n) {
      return cons(n, memo(new Callable<Cons>() {public Cons call() throws Exception {
        return intfrom(n+1L);
    }}));}

    public static Cons ssum(Cons a, Cons b) {
      return cons((long)a.car+(long)b.car, memo(new Callable<Cons>() {public Cons call() throws Exception {
        return ssum(stail(a), stail(b));
    }}));}

    public static Cons fibs = cons(0L, cons(1L,
        memo(new Callable<Cons>() {public Cons call() throws Exception {
        return ssum(stail(fibs), fibs);  
    }})));

    public static Cons fibgen(long a, long b) {
      return cons(a, memo(new Callable<Cons>() {public Cons call() throws Exception {
        return fibgen(b, a+b);
    }}));}

    public static Cons sk (long k, Cons s) {
      return cons(k*(long)s.car, memo(new Callable<Cons>() {public Cons call() throws Exception {
        return sk(k, stail(s));
    }}));}

    public static Cons merge (Cons a, Cons b) {
      long ca = (long) a.car;
      long cb = (long) b.car;
      return
      (ca<cb) ? cons(ca, memo(new Callable<Cons>() {public Cons call() throws Exception {return merge(stail(a), b);}})) :
      (ca>cb) ? cons(cb, memo(new Callable<Cons>() {public Cons call() throws Exception {return merge(a, stail(b));}})) :
                cons(ca, memo(new Callable<Cons>() {public Cons call() throws Exception {return merge(stail(a), stail(b));}}));
    }

    public static Cons hamm = cons(1L, memo(new Callable<Cons>() {public Cons call() throws Exception {
        return merge(sk(2,hamm), merge(sk(3,hamm), sk(5,hamm)));  
    }}));
    
    public static void prn(Object o) {System.out.println(o);}
    
    public static void main(String args[]) {
      prn("Поток единиц"); prn(stake(10, ones));
      prn("Поток натурального ряда"); prn(stake(20, intfrom(1L)));
      prn("Поток чисел Фибоначчи (экспоненциальный алгоритм)"); prn(stake(80, fibs));
      prn("Поток чисел Фибоначчи (линейный алгоритм)"); prn(stake(80, fibgen(0L,1L)));
      prn("Поток чисел Хэмминга"); prn(stake(1000, hamm));
    }
}
 

Результаты

(Оффтоп)

Поток единиц
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Поток натурального ряда
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
Поток чисел Фибоначчи (экспоненциальный алгоритм)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842, 10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141, 117669030460994, 190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657, 2111485077978050, 3416454622906707, 5527939700884757, 8944394323791464, 14472334024676221]
Поток чисел Фибоначчи (линейный алгоритм)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842, 10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141, 117669030460994, 190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657, 2111485077978050, 3416454622906707, 5527939700884757, 8944394323791464, 14472334024676221]
Поток чисел Хэмминга
[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60, 64, 72, 75, 80, 81, 90, 96, 100, 108, 120, 125, 128, 135, 144,150, 160, 162, 180, 192, 200, 216, 225, 240, 243, 250, 256, 270, 288, 300, 320,324, 360, 375, 384, 400, 405, 432, 450, 480, 486, 500, 512, 540, 576, 600, 625,640, 648, 675, 720, 729, 750, 768, 800, 810, 864, 900, 960, 972, 1000, 1024, 1080, 1125, 1152, 1200, 1215, 1250, 1280, 1296, 1350, 1440, 1458, 1500, 1536, 1600, 1620, 1728, 1800, 1875, 1920, 1944, 2000, 2025, 2048, 2160, 2187, 2250, 2304, 2400, 2430, 2500, 2560, 2592, 2700, 2880, 2916, 3000, 3072, 3125, 3200, 3240, 3375, 3456, 3600, 3645, 3750, 3840, 3888, 4000, 4050, 4096, 4320, 4374, 4500, 4608, 4800, 4860, 5000, 5120, 5184, 5400, 5625, 5760, 5832, 6000, 6075, 6144, 6250, 6400, 6480, 6561, 6750, 6912, 7200, 7290, 7500, 7680, 7776, 8000, 8100, 8192, 8640, 8748, 9000, 9216, 9375, 9600, 9720, 10000, 10125, 10240, 10368, 10800, 10935, 11250, 11520, 11664, 12000, 12150, 12288, 12500, 12800, 12960, 13122, 13500, 13824, 14400, 14580, 15000, 15360, 15552, 15625, 16000, 16200, 16384, 16875, 17280, 17496, 18000, 18225, 18432, 18750, 19200, 19440, 19683, 20000, 20250, 20480, 20736, 21600, 21870, 22500, 23040, 23328, 24000, 24300, 24576, 25000, 25600, 25920, 26244, 27000, 27648, 28125, 28800, 29160, 30000, 30375, 30720, 31104, 31250,32000, 32400, 32768, 32805, 33750, 34560, 34992, 36000, 36450, 36864, 37500, 38400, 38880, 39366, 40000, 40500, 40960, 41472, 43200, 43740, 45000, 46080, 46656, 46875, 48000, 48600, 49152, 50000, 50625, 51200, 51840, 52488, 54000, 54675, 55296, 56250, 57600, 58320, 59049, 60000, 60750, 61440, 62208, 62500, 64000, 64800, 65536, 65610, 67500, 69120, 69984, 72000, 72900, 73728, 75000, 76800, 77760, 78125, 78732, 80000, 81000, 81920, 82944, 84375, 86400, 87480, 90000, 91125, 92160, 93312, 93750, 96000, 97200, 98304, 98415, 100000, 101250, 102400, 103680, 104976, 108000, 109350, 110592, 112500, 115200, 116640, 118098, 120000, 121500, 122880, 124416, 125000, 128000, 129600, 131072, 131220, 135000, 138240, 139968, 140625, 144000, 145800, 147456, 150000, 151875, 153600, 155520, 156250, 157464, 160000, 162000, 163840, 164025, 165888, 168750, 172800, 174960, 177147, 180000, 182250, 184320, 186624, 187500, 192000, 194400, 196608, 196830, 200000, 202500, 204800, 207360, 209952, 216000, 218700, 221184, 225000, 230400, 233280, 234375, 236196, 240000, 243000, 245760, 248832, 250000, 253125, 256000, 259200, 262144, 262440, 270000, 273375, 276480, 279936, 281250, 288000, 291600, 294912, 295245, 300000, 303750, 307200, 311040, 312500, 314928, 320000, 324000, 327680, 328050, 331776, 337500, 345600, 349920, 354294, 360000, 364500, 368640, 373248, 375000, 384000, 388800, 390625, 393216, 393660, 400000, 405000, 409600, 414720, 419904, 421875, 432000, 437400, 442368, 450000, 455625, 460800, 466560, 468750, 472392, 480000, 486000, 491520, 492075, 497664, 500000, 506250, 512000, 518400, 524288, 524880, 531441, 540000, 546750, 552960, 559872, 562500, 576000, 583200, 589824, 590490, 600000, 607500, 614400, 622080, 625000, 629856, 640000, 648000, 655360, 656100, 663552, 675000, 691200, 699840, 703125, 708588, 720000, 729000, 737280, 746496, 750000, 759375, 768000, 777600, 781250, 786432, 787320, 800000, 810000, 819200, 820125, 829440, 839808, 843750, 864000, 874800, 884736, 885735, 900000, 911250, 921600, 933120, 937500, 944784, 960000, 972000, 983040, 984150, 995328, 1000000, 1012500, 1024000, 1036800, 1048576, 1049760, 1062882, 1080000, 1093500, 1105920, 1119744, 1125000, 1152000, 1166400, 1171875, 1179648, 1180980, 1200000, 1215000, 1228800, 1244160, 1250000, 1259712, 1265625, 1280000, 1296000, 1310720,1312200, 1327104, 1350000, 1366875, 1382400, 1399680, 1406250, 1417176, 1440000, 1458000, 1474560, 1476225, 1492992, 1500000, 1518750, 1536000, 1555200, 1562500, 1572864, 1574640, 1594323, 1600000, 1620000, 1638400, 1640250, 1658880, 1679616, 1687500, 1728000, 1749600, 1769472, 1771470, 1800000, 1822500, 1843200, 1866240, 1875000, 1889568, 1920000, 1944000, 1953125, 1966080, 1968300, 1990656, 2000000, 2025000, 2048000, 2073600, 2097152, 2099520, 2109375, 2125764, 2160000, 2187000, 2211840, 2239488, 2250000, 2278125, 2304000, 2332800, 2343750, 2359296, 2361960, 2400000, 2430000, 2457600, 2460375, 2488320, 2500000, 2519424, 2531250, 2560000, 2592000, 2621440, 2624400, 2654208, 2657205, 2700000, 2733750, 2764800,2799360, 2812500, 2834352, 2880000, 2916000, 2949120, 2952450, 2985984, 3000000, 3037500, 3072000, 3110400, 3125000, 3145728, 3149280, 3188646, 3200000, 3240000, 3276800, 3280500, 3317760, 3359232, 3375000, 3456000, 3499200, 3515625, 3538944, 3542940, 3600000, 3645000, 3686400, 3732480, 3750000, 3779136, 3796875, 3840000, 3888000, 3906250, 3932160, 3936600, 3981312, 4000000, 4050000, 4096000, 4100625, 4147200, 4194304, 4199040, 4218750, 4251528, 4320000, 4374000, 4423680, 4428675, 4478976, 4500000, 4556250, 4608000, 4665600, 4687500, 4718592, 4723920, 4782969, 4800000, 4860000, 4915200, 4920750, 4976640, 5000000, 5038848, 5062500, 5120000, 5184000, 5242880, 5248800, 5308416, 5314410, 5400000, 5467500, 5529600,5598720, 5625000, 5668704, 5760000, 5832000, 5859375, 5898240, 5904900, 5971968, 6000000, 6075000, 6144000, 6220800, 6250000, 6291456, 6298560, 6328125, 6377292, 6400000, 6480000, 6553600, 6561000, 6635520, 6718464, 6750000, 6834375, 6912000, 6998400, 7031250, 7077888, 7085880, 7200000, 7290000, 7372800, 7381125, 7464960, 7500000, 7558272, 7593750, 7680000, 7776000, 7812500, 7864320, 7873200, 7962624, 7971615, 8000000, 8100000, 8192000, 8201250, 8294400, 8388608, 8398080, 8437500, 8503056, 8640000, 8748000, 8847360, 8857350, 8957952, 9000000, 9112500, 9216000, 9331200, 9375000, 9437184, 9447840, 9565938, 9600000, 9720000, 9765625, 9830400, 9841500, 9953280, 10000000, 10077696, 10125000, 10240000, 10368000, 10485760, 10497600, 10546875, 10616832, 10628820, 10800000, 10935000, 11059200, 11197440, 11250000, 11337408, 11390625, 11520000, 11664000, 11718750, 11796480, 11809800, 11943936, 12000000, 12150000, 12288000, 12301875, 12441600, 12500000, 12582912, 12597120, 12656250, 12754584, 12800000, 12960000, 13107200, 13122000, 13271040, 13286025, 13436928, 13500000, 13668750, 13824000, 13996800, 14062500, 14155776, 14171760, 14348907, 14400000, 14580000, 14745600, 14762250, 14929920, 15000000, 15116544, 15187500, 15360000, 15552000, 15625000, 15728640, 15746400, 15925248, 15943230, 16000000, 16200000, 16384000, 16402500, 16588800, 16777216, 16796160, 16875000, 17006112, 17280000, 17496000, 17578125, 17694720, 17714700, 17915904, 18000000, 18225000, 18432000, 18662400, 18750000, 18874368, 18895680, 18984375, 19131876, 19200000, 19440000, 19531250, 19660800, 19683000, 19906560, 20000000, 20155392, 20250000, 20480000, 20503125, 20736000, 20971520, 20995200, 21093750, 21233664, 21257640, 21600000, 21870000, 22118400, 22143375, 22394880, 22500000, 22674816, 22781250, 23040000, 23328000, 23437500, 23592960, 23619600, 23887872, 23914845, 24000000, 24300000, 24576000, 24603750, 24883200, 25000000, 25165824, 25194240, 25312500, 25509168, 25600000, 25920000, 26214400, 26244000, 26542080, 26572050, 26873856, 27000000, 27337500, 27648000, 27993600, 28125000, 28311552, 28343520, 28697814, 28800000, 29160000, 29296875, 29491200, 29524500, 29859840, 30000000, 30233088, 30375000, 30720000, 31104000, 31250000, 31457280, 31492800, 31640625, 31850496, 31886460, 32000000, 32400000, 32768000, 32805000, 33177600, 33554432, 33592320, 33750000, 34012224, 34171875, 34560000, 34992000, 35156250, 35389440, 35429400, 35831808, 36000000, 36450000, 36864000, 36905625, 37324800, 37500000, 37748736, 37791360, 37968750, 38263752, 38400000, 38880000, 39062500, 39321600, 39366000, 39813120, 39858075, 40000000, 40310784, 40500000, 40960000, 41006250, 41472000, 41943040, 41990400, 42187500, 42467328, 42515280, 43046721, 43200000, 43740000, 44236800, 44286750, 44789760, 45000000, 45349632, 45562500, 46080000, 46656000, 46875000, 47185920, 47239200, 47775744, 47829690, 48000000, 48600000, 48828125, 49152000, 49207500, 49766400, 50000000, 50331648, 50388480, 50625000, 51018336, 51200000]

[_Ivana]

фикс (скопировал предыдущую версию, а отредактировать уже нельзя) - в мемо надо добавить строку

Используется синтаксис Java

this.calculated = true;

куда надо

[arseniiv]

Munin в сообщении #1377874 писал(а):

Подойдёт на Java или C#.

C# будет читерством, потому что в какую-то версию .net ввели тип Lazy<T> (хотя его можно было написать и раньше, конечно). Может быть неудобно писать lazyThing = new Lazy<...>(() => выражение) вместо выражение и потом обращаться как lazyThing.Value (например в Idris, как я читал, преобразования между Lazy a и a неявные), но для такого языка и для обычной редкости использования такие предупреждения, что именно происходит, наверно в самый раз.

После этого мы можем написать

Используется синтаксис C#

class Stream<T> {
  public T First { get; private set; }
  public Lazy<Stream<T>> Rest { get; private set; }
  public Stream(T first, Func<Stream<T>> rest) {
    First = first;
    Rest = new Lazy<Stream<T>>(rest);
  }
  public Stream<U> Map<U>(Func<T, U> f) =>
    new Stream<U>(f(First), () => Rest.Map(f));
}

// ascending = 0 : map (+ 1) ascending
var ascending = new Stream<int>(0, () => ascending.Map(n => n + 1));

// loop = False : True : loop
var loop = new Stream<bool>(false, () => new Stream(true, () => loop));

Писал из головы, потому могут быть небольшие ошибки, которые легко исправить. Плюс это можно даже сделать выглядящим чуть красивее. Но вообще для конкретно этой цели есть итераторы.

[warlock66613]

arseniiv, не пойдёт: Value у Lazy - это вычисляемое свойство, а не поле и не тривиальное свойство-обёртка над полем, так что оно уже не часть дерева.

-- 23.02.2019, 14:25 --

Но я-то имел в виду именно Хаскелл. Убрав фичу ленивости рантайма, вы потеряете возможность создавать структуры данных бесконечной вложенности: рантайм будет на них зацикливаться/зарекурсиваться. Также изменятся тайминги и использование памяти. Но больше никакой разницы вы не заметите - и это важно понимать, чтобы не приплетать ленивость к перпендикулярным ей вещам вроде монад.

[Munin]

_Ivana
Спасибо, убедительно. Буду разбираться.

[arseniiv]

warlock66613 в сообщении #1377914 писал(а):

Value у Lazy - это вычисляемое свойство, а не поле и не тривиальное свойство-обёртка над полем, так что оно уже не часть дерева.

Хм, ну, я и не думал воспринимать буквально, в конце концов если сам рантайм не переписывает графы или не делает что-то эквивалентное, то в строгом смысле такое дерево не построить, и обсуждать тут действительно нечего, но если говорить о чём-то, ведущем себя эквивалентно (кроме никак не убираемого одного слоя индирекции), то почему нет.

А так да, конечно.

[warlock66613]

Тут на Хабре проскочила интересная ссылка на книгу Category Theory for Programmers. Судя по оглавлению, эта книга не является учебником теории категорий, и вот именно её программисту почитать не помешало бы - по крайней мере такому, кто уже начал осваивать хотя бы один функциональный язык (хотя бы тот же F#).