Czy cały kod może być reprezentowany jako seria operacji Map / Filter / Reduce?

16

Ostatnio refaktoryzowałem duże fragmenty kodu i zastępowałem je zapytaniami Linq.

Usuwanie uprzedzeń językowych - Linq jest zasadniczo zestawem operacji Map / Filter i Reduce, które działają na sekwencji danych.

To dało mi do myślenia, jak daleko teoretycznie byłbym w stanie to zrobić. Czy byłbym w stanie przepisać całą bazę kodu na serię (lub nawet jedną) operacji Map / Filter i Reduce.

Niestety dostaję wynagrodzenie za robienie użytecznych rzeczy, więc nie byłem w stanie dużo więcej eksperymentować, ale nie mogę wymyślić żadnej struktury kodu, która nie mogłaby zostać zrestrukturyzowana jako taka. Kod działający po stronie może być przetwarzany przez monady. Nawet dane wyjściowe zasadniczo mapują adresy pamięci na adresy ekranowe.

Czy jest coś, czego nie można (teoretycznie) przepisać jako zapytanie Linq?

computer-science Mongus Pong
źródło
Drzewa patrz tutaj: stackoverflow.com/questions/250377/...
blueberryfields
Zawsze myślałem, że „redukcja” jest wystarczająca, aby zagwarantować ukończenie Turinga (mapa i filtr mogą być zaimplementowane jako operacje redukujące, nie?) - przynajmniej funkcjonalny odpowiednik redukcji. Nie wiem wystarczająco dużo o Linq, aby mieć pewność, jak ściśle implementacja jest zgodna z funkcjonalną.
blueberryfields
1
Nie wiem, ale ogólną zasadą jest to, że wszystko, co ktokolwiek rozważałby nawet napisanie całego swojego kodu, okaże się kompletne. Ale konsekwencją tego jest to, że ukończenie Turinga nie jest zbyt ekscytujące.
psr
1
Zgadzam się z psr; Myślę, że ważna odpowiedź na to pytanie musi dotyczyć kompletności Turinga. Dowodem może być próba wdrożenia maszyny Turinga przy użyciu tylko tych operacji.
Rob
Idle pomyślał: nawet jeśli pozwolimy na takie bzdury my_list.map(_ignored => a copy of my_list), wydaje się, że użycie takiego programu przez przestrzeń jest ograniczone przez wielomian (w zależności od długości programu). Wtedy taki język z pewnością nie byłby w stanie obliczyć problemów, których nie ma w PSPACE. Ponieważ jednak wiele problemów w PSPACE uważa się za nierozwiązywalne, nie wspominając o większych klasach, może to nie być bardzo poważne ograniczenie.

Odpowiedzi:

1

Nazywa się to programowaniem funkcjonalnym i przez wielu jest uważane za fundamentalną koncepcję. oto dobre wprowadzenie do Joel On Software . Bardziej techniczna odpowiedź brzmi „nie”, nie ma obecnie znanego sposobu zadawania komputerowi pytań (w dobrze określony sposób), na które nie można odpowiedzieć za pomocą rachunku SKI.

JP Mcgrady
źródło
1
Jest o wiele bardziej funkcjonalny niż do programowania funkcji map, filteroraz reduce(to idzie trzykrotnie jeśli zignorujemy Kompletność Turinga i użyć praktycznych języków FP). W rzeczywistości są one po prostu dość ogólne, a zatem ogólnie przydatne, ale w rzeczywistości są bardzo prostymi aplikacjami programowania funkcjonalnego. Nagi minimalny rachunek lambda może zdefiniować te funkcje wśród wielu innych, a nie na odwrót.
„oto dobre wprowadzenie do Joel On Software” - które udaje się pomylić Fortran z Basicem, więc nie ufałbym innym faktom.
quant_dev