Wątek przeniesiony 2021-04-03 15:26 z Algorytmy i struktury danych przez somekind.

Programowanie funkcyjne - dywagacje początkującego.

2

Dla fanów książek:

  • https://www.cs.nott.ac.uk/~pszgmh/pih.html (Programming in Haskell 2nd edition, tak naprawdę wprowadzenie do programowania funkcyjnego, sporo rzeczy pominiętych np. efekty, monad transformers ale dla kogoś kto nie miał w ogóle styczności z FP to i tak będzie aż za dużo materiału. Najważniejsze że jest "state monad" opisany.)

  • https://haskellbook.com/ - tej pozycji jeszcze nie czytałem, ale słyszałem na HN bardzo dobre o niej opinie. Mam PDF'a spis treści wygląda bardzo obiecująco, omówione jest wszystko w tym te nieszczęsne monad transformery.

  • Functional programming in Scala - jeżeli ktoś jest fanem Scali. Tutaj moje odpowiedzi do ćwiczeń: https://github.com/marcin-chw[...]nscala/chp8/PropTesting.scala Nie polecam dla początkujących, nieco już obeznani z FP docenią tą pozycję - ta książka to tak naprawdę zeszyt ćwiczeń robisz ćwiczenia, zaczynasz rozumieć. Opisane parser combinators i property based testing, jak również równoległość. Sporo ćwiczeń wokół różnych state monad więc można się mentalnie przygotować na starcie z IO.

Generalnie miałem jakiś tam kontakt z FP w pracy więc widziałem też FP od drugiej strony:

  • W Scali nie da się mieszać różnych typów monad np. Writer i Option lub Future i Option, potrzeba Monad Transformers żeby obejść ten problem np. OptionT
  • Jeżeli już jesteśmy przy monad transformers to zaczyna się pojawiać pojęcie efektów np. Option to efekt opcjonalności a Future to efekt odroczonego wykonania programu, w kodzie oznacza to tyle że jako parametr generyczny pojawia się typ E[_] (a więc typ generyczny który przyjmuje parametr; HKT) i to na nim się operuje zamiast na Future czy Option. Tu jest wyjaśnione jak należy:
  • Modyfikacja zagnieżdżonych immutable struktur ssie i to ssie porządnie, rozwiązanie to kolejna biblioteka aka murarka funkcyjna: https://www.optics.dev/Monocle/ Tu pojawia się pojecie lens'ów a nawet prismów LOL
  • Poza znanymi Option, Either, Future (choć to nie monada) to w życiu zawodowym spotkałem jeszcze jedynie Writer'a (dodaje logi do zwracanego obiektu). Nie piszemy stricte funkcyjnie więc IO znam tylko z książek (a i to słabo).
  • Property based tests działają tyle że wolno :P Warto wiedzieć że coś takiego jest, czasami się przydaje.

Generalnie ja rozumiem że "killer feature" i "selling point" programowania funkcyjnego to możliwość rozumowania o kodzie programu. Kod ma stać się podobny do algebraicznego równania i ma podlegać ścisłym prawom matematyki. Czas zostaje niejako wyrugowany z programu. Przykładowo w programie funkcyjnym zawsze można zastąpić zmienną (a raczej stałą :P) wyrażeniem ją definiującym i nie zmieni to zachowania programu.

W praktyce wydaje mi się że praca ze stanem jest największą kulą u nogi FP (nie licząc oszołomów z category theory). Taki sposób reprezentacji programu nie jest do końca intuicyjny i wymaga sporo wysiłku żeby zostać zrozumianym. Przyklad jak wygląda losowanie liczb w wydaniu funkcyjnym: https://github.com/marcin-chw[...]k/fpinscala/chp6/Random.scala

2
katakrowa napisał(a):
  1. Gdzie znaleźć przykłady "większych" programów napisanych z zastosowaniem tego paradygmatu? Proste przykłady są piękne ale chciałbym zobaczyć starcie tego typu programowania np. z bazą danych, plikami, HTTP.

Brick jest dosyć prosty i ma listę projektów.
Beam to idealny przykład jak funkcyjnie obchodzić się z z bazami. Bez magii.
Oprócz tego postgrest/hasura.

  1. Jak głęboko zakorzeniać funkcyjność w swoim programie? Na jakim poziomie warto to stosować? Czy jedynie jako odgórną koncepcję czy jednak faktyczną implementację "wszystkiego"?

To zależy tylko i wyłącznie od tego, w jakim języku będziesz programować. W haskellu używanie funkcyjnych abstrakcji jest optymalne. Stosowanie ich np. w js-e da taki sam rezultat, jakbyś chciał klepać oop w haskellu.

4

Zależy o które "programowanie funkcyjne" chodzi. Bo mamy (z mojej perspektywy) 2 wiodące nurty:

  • Typed FP, które skupia się na praktycznie dowodzeniu tego, że program jest poprawny w czasie kompilacji poprzez system typów. Mamy teorię kategorii tutaj i wszystkie zabawy związane z tym, jak monady, funktory, etc. Przykładem języka, który idzie w tę stronę jest np. Haskell, Scala też, ale mniej hardcorowa
  • Untyped FP, gdzie bardziej skupiamy się na samej niemutowalności i fakcie, że funkcja może być wartością. Przykładami tutaj mogą być różnego rodzaju Lispy czy języki oparte o BEAM (Erlang, Elixir, LFE, Gleam, etc.)

W zależności od tego, które rozwiązanie Ciebie interesuje bardziej, twoje pytania będą miały różne odpowiedzi. Ja mogę się więcej wypowiedzieć o Untyped FP, jako, że to jest mój główny zbiór w tym momencie.

Więc jeśli chodzi o Erlanga/Elixira, to:

  1. Masz całe mnóstwo bibliotek i mniejszych lub większych projektów - RabbitMQ, CouchDB, MongooseIM, ejabberd, Plausible, Logflare tak na początek. Oprócz tego jest trochę komercyjnych projektów jak WhatsApp, Klarna, Discord, etc. Ogólnie HTTP bardzo ładnie mapuje na FP, bo koncepcyjnie każde zapytanie jest niezależne i wszystkie dane potrzebne do jego obsłużenia są w zapytaniu, na tej bazie opiera się całe FaaS. W językach jak Erlang/Elixir to jest to podstawa całej pracy, bo każde zapytanie to jest niezależny proces, co pozwala nam na bardzo łatwą obsługę i izolację błędów.
  2. Zależy od projektu, ale ogólnie dobrym podejściem na pewno jest "functional core", gdzie sama logika biznesowa jest funkcyjna jak się da i ogranicza efekty uboczne do niezbędnego minimum. Dzięki temu jest taki system łatwiej testować. Co do "warstw zewnętrznych" - to już zależy, bo czasem lepiej będzie mieć tam więcej funkcyjności (jak np. ww. HTTP), a czasem nie (np. niektóre podejścia do GUI).
0
Aleksander32 napisał(a):

@katakrowa @cerrato @jarekr000000 @KamilAdam
znalazłem (ponoć, nie weryfikowałem czy działa :P) implementacje Quake w Haskellu
https://github.com/ocharles/zero-to-quake-3

O ile mogę uwierzyć, że kod funkcyjny jest zwięźlejszy niż OOP to już absolutnie nie uwierzę w to, że 95k kodu w Haksell jest implementacją Quake, o którym myślę :-)

1

W pracy używam C# oraz Pythona i przełączanie umysłu pomiędzy tymi językami nie sprawia mi większego problemu. Natomiast przestawianie umysłu z C# na Haskella byłoby dla mnie problematyczne. Jestem przyzwyczajony do imperatywnego sposobu myślenia. Chcąc programować w Haskellu musiałbym zrezygnować z używania języków imperatywnych. Jak ktoś chce to i w C# może programować funkcyjne. W Pythonie mam list comprehension oraz funkcje: map, filter, zip, fold... i to mi na razie wystarczy.

1

No to pierwsze próby mam za sobą i wygląda na to, że jest to porażka.
Miało być małe czyste funkcyjne a wyszedł jakiś koszmar i programistyczny kulfon...
Może i godzina na naukę nie jest najlepsza ale mimo wszystko śmiać mi się chce z tego co wyszło wskutek przekształceń aby kod spełniał "założenia" .
Coś czuję, że nie o to w tym chodzi :-)

https://jsfiddle.net/koj632fr/

Są jednak pierwsze wnioski.

  1. Przekazywanie w JS obiektów przez referencje nie ułatwia sprawy. Nie mam pojęcia jak to ugryźć? Robić kopie obiektów przy przekazywaniu do funkcji czy jak?
  2. Usilne pozbywanie się zmiennych lokalnych var i let chyba bardziej zaciemnia kod niż robi czytelnym.
  3. Szczerze mówiąc przy oprogramowywanym zagadnieniu, które od jest w dużej mierze "matematyczne" wcale nie jest łatwo wymyślić koncepcję aby wszystko było zgodne z paradygmatem.
  4. Tak samo sugestie korzystania z forEach zamiast for... Przecież on wywołuje funkcje, której rezultatu nie złapiemy... Żaby zrobić zgodnie z paradygmatem to już chyba for będzie 100 razy czytelniejszy.

Albo całkiem z d...y strony do tego podchodzę albo coś jest nie tak...

var Graph = new classGraph( document.getElementById("screen") );
var pm = { "x":0, "y":0, "z":0, "s":5, "xC":Graph.maxX/2, "yC":Graph.maxY/2 } ;   

function drawTriangle( tr, pm ){
  var x0 = pm [ 'xC' ] + tr['pts'][0]['x'] * pm [ 's' ] * 800/(500+tr['pts'][0]['z']);
  var y0 = pm [ 'yC' ] + tr['pts'][0]['y'] * pm [ 's' ] * 800/(500+tr['pts'][0]['z']);
  var x1 = pm [ 'xC' ] + tr['pts'][1]['x'] * pm [ 's' ] * 800/(500+tr['pts'][1]['z']);
  var y1 = pm [ 'yC' ] + tr['pts'][1]['y'] * pm [ 's' ] * 800/(500+tr['pts'][1]['z']);
  var x2 = pm [ 'xC' ] + tr['pts'][2]['x'] * pm [ 's' ] * 800/(500+tr['pts'][2]['z']);
  var y2 = pm [ 'yC' ] + tr['pts'][2]['y'] * pm [ 's' ] * 800/(500+tr['pts'][2]['z']);
  var g = Math.round ( 64 - tr['pts'][0]['z']/2 ) ;
  Graph.triangleFilled ( x0, y0, x1, y1, x2, y2, "rgba(100,"+g+",100,0.2" );
  Graph.triangle ( x0, y0, x1, y1, x2, y2, "rgba(255,"+g+",100,0.6)" );
}

function ptRotate ( pt, angle, da, db ){
  var tmp = pt[da] * Math.cos( angle ) + pt[db] * Math.sin( angle );  
  pt[db] = pt[db] * Math.cos( angle ) - pt[da]* Math.sin( angle );
  pt[da] = tmp;
}

function rotate( scene, pm ){
  scene.forEach ( function( tr ){
    [ ['x','y','z'],['y','x','z'],['z','x','y'] ].forEach( function( el ){ 
      tr['pts'].forEach ( function( pt ){ ptRotate ( pt, pm[el[0]], el[1], el[2] );} );
    } );
  } );
  return scene ;
}

function sceneRender( scene, pm ){  
  Graph.clearScr();
  scene.forEach( function ( tr ) { drawTriangle ( tr, pm ); } );
}

function animation( scene, pm, form ){
  ['x','y','z'].forEach( function(el){ pm [ el ] = pm [ el ] + ( form[el].checked ? 0.01 : 0 ); });
  pm [ 's' ] = parseFloat( form['s'].value )/10 ;
  sceneRender ( rotate ( JSON.parse ( JSON.stringify ( scene ) ), pm ), pm );
}

setInterval ( function(){ animation( scene, pm, document.getElementById ( "formParameters" ) ); }, 50 );
<!DOCTYPE html>
  <head>
    <meta http-equiv='Content-Type' content='text/html; charset=utf-8'>
    <title>Functional programming - test0001.</title>
    <link rel='stylesheet' type='text/css' href='style.css'>    
    </head>
    <body>
    <form id='formParameters'>
      <input type='checkbox' id='x' name='x' checked=checked><label for='x'>Rotate X</label>
      <input type='checkbox' id='y' name='y'><label for='y'>Rotate Y</label>
      <input type='checkbox' id='z' name='z' checked=checked><label for='z'>Rotate Z</label>
      <input type='number' id='s' name='s' min=1 max=250 value=25><label for='s'>Scale</label>
    </form>
    <canvas id="screen"></canvas>  
  </body>
  <script src='graph.js'></script>
  <script src='scene.js'></script>
  <script src='script.js'></script>
</html>

CSS, dane i wsparcie rysowania grafiki w załączniku.

0

@WeiXiao:
Zapewne tak... jak i same parametry obrotów i skalowania. Same dane punktów przekazuję "jak trzeba" ale ta grafika, interakcja z użytkownikiem... Ch. wie jak to ugryźć?

5

@katakrowa:
Twój przykład z programowaniem funkcyjnym ma niewiele wspólnego, trudno wyciągać wnioski.
Problem jest taki, że goły JS nie za bardzo fp wspiera. Da się, ale trzeba relatywnie dużo dopisać, a zysk niewielki.
Dlatego, na początek lepiej jest wybrać sobie język, który ma dobre wsparcie dla fp i w nim poćwiczyć. A potem przenieść sobie co trzeba na js czy inny język.
Zobacz przykład "z tej działki" w ELM
https://elm-lang.org/examples/cube

FP na froncie najczęściej robie w ScalaJS + React, ale czasem w TypeScript + React (to drugie troche gorsze, ale bardziej popularne).

Odnośnie punktów:

  1. Przekazywanie w JS obiektów przez referencje nie ułatwia sprawy. Nie mam pojęcia jak to ugryźć? Robić kopie obiektów przy przekazywaniu do funkcji czy jak?

Przekazywanie przez referencje nie jest żadnym problemem - ważne, żeby obiektów nie mutować. W JS masz Object.freeze(obj); żeby zrobić niemutowalnym obj. Nie musisz z tego korzystać, ale możesz (wywołujesz freeze po stworzeniu np. w konstruktorze).

  1. Usilne pozbywanie się zmiennych lokalnych var i let chyba bardziej zaciemnia kod niż robi czytelnym.

To jest raczej kwestia przyzwyczajenia - mimo dwudziestu kilku lat pisania imperatywnego, teraz po paru latach fp nawet nie umiem sobie ze "zmiennymi" radzić. Ważne, że mając niemutowalne wartości dużo mniej musisz mieć w pamięci analizując kod. Więc nawet jak jest zagmatwany to na mniej elementów trzeba zwracać uwagę. Na początku zabawy w fp nie widać tej zalety, bo twój mózg jest nadal przyzwyczajony do mozolnego układania sobie stanu w głowie, nie da się tego łatwo wyłączyć. W efekcie męczysz się niepotrzebnie.

  1. Szczerze mówiąc przy oprogramowywanym zagadnieniu, które od jest w dużej mierze "matematyczne" wcale nie jest łatwo wymyślić koncepcję aby wszystko było zgodne z paradygmatem.

No tutaj na razie wiele Ci nie wyszło, ale moim zdaniem to wynik użycia złej technologii do nauki. JS nie jest najgorszym językiem do fp, jak już wiesz o co chodzi. Niestety na początku nie pomaga Ci, a wręcz przeszkadza.

  1. Tak samo sugestie korzystania z forEach zamiast for... Przecież on wywołuje funkcje, której rezultatu nie złapiemy... Żaby zrobić zgodnie z paradygmatem to już chyba for będzie 100 razy czytelniejszy.

forEach też nie jest wielce funkcyjne :-) - jest o krok lepsze od pętli for, ale nadal zakłada efekt uboczny. map jest funkcyjne.

Twój kod nadaje się do przerobienia na fp, ale trzeba by dodać odpowiednie biblioteki, które uzupełniają to czego w języku nie ma.
1) funkcyjne struktury danych
https://immutable-js.github.io/immutable-js/
2) monada io na operacje na canvasie
tu masz przykład
https://dev.to/imax153/graphi[...]or-the-html-5-canvas-api-1832

ale moim zdaniem naprawdę lepiej zacząć od czystego jezyka.

8

@katakrowa: bardzo jest nie tak, bo mutujesz wartości zamiast tworzyć nowe obiekty.

Nie za bardzo znam się na grafice, ale to by wyglądało mniej więcej tak:

const createPoint = (x, y, z) => [x, y, z]
const createTriangle = (a, b, c) => ({points: [a, b, c], type: 'triangle'})

const rotXMatrix = (theta) => [
  [1, 0, 0],
  [0, Math.cos(theta), -Math.sin(theta)],
  [0, Math.sin(theta), Math.cos(theta)]
]
const rotYMatrix = (theta) => [/* as above */]
const rotZMatrix = (theta) => [/* as above */]

const rotate = (object, matrix) => {
  const points = object.points.map((point) => matrixMultiply(matrix, point))
  return {...object, points}
}

const translate = (object, [tx, ty, tz]) => {
  const points = object.points.map(([px, py, pz]) => [px + tx, py + ty, pz + tz])
  return {...object, points}
} 

/* etc. */

Wtedy możesz np. narysować trójkąt w odpowiednim miejscu poprzez:

const triangle = createTriangle(createPoint(0, 0, 0), createPoint(1, 0, 0), createPoint(0, 1, 0))
const rotated = rotate(triangle, rotZMatrix(Math.PI / 2))
const translated = translate(rotated, [1, 2, 3])

draw(context, translated)

Przy czym zauważ, że za każdym razem tworzymy nowy obiekt, więc z "jednego trójkąta" można utworzyć wszystkie, bo nie "modyfikujesz oryginału".

0

Mam świadomość tego, że funkcje, które zaproponowałem mutują... Tylko jak zrobić w JS inaczej?

Na początek uprośćmy przykład do minimum i zrezygnujmy z interfejsu użytkownika i "rysowania" czyli interfejsu graficznego.
Czyli na wejściu do programu mamy tablicę trójkątów oraz parametry przekształcenia dla kolejnych kroków ( nasze dane )...

//
// Trzy trójkąty, każdy składa się z 3 punktów, każdy punkt określony pozycją w przestrzeni 3D:
var scene = [
  {
    "pts":[
          {"x":0.0000000000,"y":0.0000000000,"z":83.5137273309},
          {"x":25.5195242506,"y":0.0000000000,"z":33.4054909323},
          {"x":7.8859666818,"y":24.2705098312,"z":33.4054909323}
    ]},
  {
    "pts":[
          {"x":0.0000000000,"y":0.0000000000,"z":83.5137273309},
          {"x":7.8859666818,"y":24.2705098312,"z":33.4054909323},
          {"x":-20.6457288071,"y":15.0000000000,"z":33.4054909323}
    ]},
  {
    "pts":[
          {"x":0.0000000000,"y":0.0000000000,"z":83.5137273309},
          {"x":-20.6457288071,"y":15.0000000000,"z":33.4054909323},
          {"x":-20.6457288071,"y":-15.0000000000,"z":33.4054909323}
    ]}
]

//
// kąt obrotów wokół osi x, y, z oraz skalowanie:
var displayParameters = {
 "rotateX":0.25,
 "rotateY":.25,
 "rotateZ":.25,
 "zoom":2
}

W jaki sposób napisać czystą funkcję, która zwróci tablicę z przekształconymi wartościami?
Dość jasne jest, że samo przekazanie zmiennych scene i displayParameters już nie jest "czyste" bo JS przekazuje referencję a nie wartość. Zatem nawet jeśli troszkę oszukamy i zrobimy funkcjęm która skopiuje i wyprodukuje nam taki niemutowalny obiekt:

function _cp ( any ){
  return Object.freeze( JSON.parse ( JSON.stringify ( any ) ) );
}

i zastosujemy ją przy przekazywaniu parametrów do funkcji w następujący sposób:

function transform( scene, displayParameters ){
  // tu jakoś przekształcamy scene bez foreach i for i robimy z niego newScene... Tylko JAK ?
  return newScene ; //
}

let newScene = transform ( _cp ( scene ), _cp ( displayParameters ) );

to do tego momentu mamy spełnione wszelkie założenia...
Utkwiłem jednak na forEach / for ... Jak wewnątrz funkcji transform przekształcić wszystkie elementy aby zrobić to zgodnie "ze sztuką"?
Niech dla przykładu to będzie najłatwiejsze przekształcenie polegające na dodaniu do każdej wartości X wartość 1 do Y wartość 2 a do Z wartość 3.

Czyli odpowiednik kodu nie spełniającego założeń progrqmowania funkcyjnego:

function transform( scene, displayParameters ){
  scene.forEach( function ( x ) { 
    console.log ( x);
    x.pts[0]['x'] += 1;
    x.pts[0]['y'] += 2;
    x.pts[0]['z'] += 3;
    x.pts[1]['x'] += 1;
    x.pts[1]['y'] += 2;
    x.pts[1]['z'] += 3;
    x.pts[2]['x'] += 1;
    x.pts[2]['y'] += 2;
    x.pts[2]['z'] += 3;
  } );
  // tu jakoś przekształcamy scene bez foreach i for i robimy z niego newScene... Tylko JAK ?
  return scene ; //
}

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0