Dlaczego nie ma klasy dla funkcji?

17

W problemach z nauką, z którymi się bawiłem, zdałem sobie sprawę, że potrzebuję kroju typowego dla funkcji z operacjami do aplikowania, komponowania itp. Powody ...

  1. Wygodne może być traktowanie reprezentacji funkcji tak, jakby była ona samą funkcją, tak że zastosowanie funkcji niejawnie korzysta z interpretera, a komponowanie funkcji daje nowy opis.

  2. Gdy masz już typ dla funkcji, możesz uzyskać pochodne typy dla specjalnych rodzajów funkcji - w moim przypadku chcę funkcji odwracalnych.

Na przykład funkcje, które stosują przesunięcia liczb całkowitych, mogą być reprezentowane przez ADT zawierający liczbę całkowitą. Zastosowanie tych funkcji oznacza po prostu dodanie liczby całkowitej. Kompozycja jest realizowana przez dodanie zawiniętych liczb całkowitych. Funkcja odwrotna ma zanegowaną liczbę całkowitą. Funkcja tożsamości otacza zero. Nie można zapewnić stałej funkcji, ponieważ nie ma dla niej odpowiedniej reprezentacji.

Oczywiście nie trzeba przeliterować rzeczy tak, jakby wartości były prawdziwymi funkcjami Haskella, ale kiedy wpadłem na ten pomysł, pomyślałem, że taka biblioteka musi już istnieć, a może nawet używać standardowych pisowni. Ale nie mogę znaleźć takiej klasy w bibliotece Haskell.

Znalazłem moduł Data.Function , ale nie ma żadnej klasy - tylko niektóre typowe funkcje, które są również dostępne z Preludium.

Więc - dlaczego nie ma klasy dla funkcji? Czy to „tylko dlatego, że nie ma” czy „ponieważ nie jest tak przydatne, jak myślisz”? A może pomysł ma fundamentalny problem?

Największym możliwym problemem, o jakim do tej pory myślałem, jest to, że aplikacja funkcji na rzeczywistych funkcjach prawdopodobnie musiałaby zostać specjalnie zaprojektowana przez kompilator, aby uniknąć problemu z zapętleniem - aby zastosować tę funkcję, muszę zastosować funkcję aplikacji funkcji, i aby to zrobić, muszę wywołać funkcję aplikacji funkcji, i aby to zrobić ...

Więcej wskazówek

Przykładowy kod pokazujący, do czego dążę ...

{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE GADTs #-}

--  In my first version, Doable only had the one argument f. This version
--  seemed to be needed to support the UndoableOffset type.
--
--  It seems to work, but it also seems strange. In particular,
--  the composition function - a and b are in the class, but c isn't,
--  yet there's nothing special about c compared with a and b.
class Doable f a b where
  fwdApply :: f a b -> a -> b
  compDoable :: f b c -> f a b -> f a c

--  In the first version, I only needed a constraint for
--  Doable f a b, but either version makes sense.
class (Doable f a b, Doable f b a) => Undoable f a b where
  bwd      :: f a b -> f b a

  bwdApply :: f a b -> b -> a
  bwdApply f b = fwdApply (bwd f) b

--  Original ADT - just making sure I could wrap a pair of functions
--  and there were no really daft mistakes.
data UndoableFn a b = UFN { getFwd :: a -> b, getBwd :: b -> a }

instance Doable UndoableFn a b where
  fwdApply = getFwd
  compDoable f g = UFN ((getFwd f) . (getFwd g)) ((getBwd g) . (getBwd f))

instance Undoable UndoableFn a b where
  bwd f    = UFN (getBwd f) (getFwd f)
  bwdApply = getBwd

--  Making this one work led to all the extensions. This representation
--  can only represent certain functions. I seem to need the typeclass
--  arguments, but also to need to restrict which cases can happen, hence
--  the GADT. A GADT with only one constructor still seems odd. Perhaps
--  surprisingly, this type isn't just a toy (except that the whole thing's
--  a toy really) - it's one real case I need for the exercise. Still a
--  simple special case though.
data UndoableOffset a b where
  UOFF :: Int -> UndoableOffset Int Int

instance Doable UndoableOffset Int Int where
  fwdApply (UOFF x) y = y+x
  compDoable (UOFF x) (UOFF y) = UOFF (x+y)

instance Undoable UndoableOffset Int Int where
  bwdApply (UOFF x) y = y-x
  bwd (UOFF x) = UOFF (-x)

--  Some value-constructing functions
--  (-x) isn't shorthand for subtraction - whoops.
undoableAdd :: Int -> UndoableFn Int Int
undoableAdd x = UFN (+x) (\y -> y-x)

undoableMul :: Int -> UndoableFn Int Int
undoableMul x = UFN (*x) (`div` x)

--  With UndoableFn, it's possible to define an invertible function
--  that isn't invertible - to break the laws. To prevent that, need
--  the UFN constructor to be private (and all public ops to preserve
--  the laws). undoableMul is already not always invertible.
validate :: Undoable f a b => Eq a => f a b -> a -> Bool
validate f x = (bwdApply f (fwdApply f x)) == x

--  Validating a multiply-by-zero invertible function shows the flaw
--  in the validate-function plan. Must try harder.
main = do putStrLn . show $ validate (undoableAdd 3) 5
          putStrLn . show $ validate (undoableMul 3) 5
          --putStrLn . show $ validate (undoableMul 0) 5
          fb1 <- return $ UOFF 5
          fb2 <- return $ UOFF 7
          fb3 <- return $ compDoable fb1 fb2
          putStrLn $ "fwdApply fb1  3 = " ++ (show $ fwdApply fb1  3)
          putStrLn $ "bwdApply fb1  8 = " ++ (show $ bwdApply fb1  8)
          putStrLn $ "fwdApply fb3  2 = " ++ (show $ fwdApply fb3  2)
          putStrLn $ "bwdApply fb3 14 = " ++ (show $ bwdApply fb3 14)

Aplikacja wymaga pewnego rodzaju unifikacji, w której zunifikowane wartości nie są równe, ale są powiązane poprzez te odwracalne funkcje - logika w stylu prologu, ale a = f(b)raczej z ograniczeniami a = b. Większość kompozycji będzie wynikać z optymalizacji struktury znajdowania związków. Potrzeba odwrotności powinna być oczywista.

Jeśli żaden element w zunifikowanym zestawie nie ma dokładnej wartości, to konkretny element może być określony ilościowo tylko w stosunku do innego elementu w tym zunifikowanym zestawie. Dlatego nie chcę używać „rzeczywistych” funkcji - obliczania tych względnych wartości. Mógłbym porzucić cały aspekt funkcji i po prostu mieć wielkości bezwzględne i względne - prawdopodobnie potrzebuję tylko liczb / wektorów i (+)- ale mój astronauta z architektury wewnętrznej chce swojej zabawy.

Jedynym sposobem, w jaki ponownie rozbijam linki, jest cofanie się i wszystko jest czyste - szukanie związku zostanie wykonane przy użyciu kluczy IntMapjako „wskaźników”. Mam proste wyszukiwanie związków, ale ponieważ nie dodałem jeszcze odwracalnych funkcji, nie ma sensu wymieniać go tutaj.

Powody, dla których nie mogę korzystać z Applicative, Monad, Arrow itp

Główne operacje, których potrzebuję, aby zapewnić klasę abstrakcji funkcji, to aplikacja i kompozycja. Brzmi to znajomo - EG Applicative (<*>), Monad (>>=)i Arrow (>>>)są wszystkie funkcje kompozycji. Jednak typy, które implementują abstrakcję funkcji w moim przypadku będą zawierać pewną strukturę danych, która reprezentuje funkcję, ale która nie jest (i nie może zawierać) funkcję, i która może reprezentować tylko pewien ograniczony zestaw funkcji.

Jak wspomniałem w objaśnieniu kodu, czasami mogę tylko określić ilościowo jeden element względem drugiego, ponieważ żaden element w „zunifikowanym” klastrze nie ma dokładnej wartości. Chcę mieć możliwość przedstawienia reprezentacji tej funkcji, która na ogół będzie kompozycją kilku zapewnionych funkcji (podchodzenie do wspólnego przodka w drzewie unii / znalezienia) i kilku funkcji odwrotnych (chodzenie z powrotem do drugiej pozycja).

Prosty przypadek - gdy oryginalne „funkcje” ograniczają się do „funkcji” z przesunięciem całkowitym, chcę, aby złożony wynik był „funkcją” z przesunięciem całkowitym - dodaj przesunięcia komponentu. To duża część tego, dlaczego funkcja kompozycji musi znajdować się w klasie, podobnie jak funkcja aplikacji.

To znaczy, że nie może dostarczyć operacji pure, returnlub arrdla moich typów, więc nie mogę używać Applicative, Monadlub Arrow.

To nie jest awaria tego typu - to niedopasowanie abstrakcji. Abstrakcja, której chcę, ma prostą, czystą funkcję. Nie ma na przykład efektów ubocznych i nie trzeba budować wygodnej notacji do sekwencjonowania i komponowania funkcji innych niż odpowiednik standardu (.), Który dotyczy wszystkich funkcji.

I może instancja Category. Jestem pewien, że wszystkie moje funkcjonalne rzeczy będą w stanie zapewnić tożsamość, chociaż prawdopodobnie jej nie potrzebuję. Ponieważ jednak Categorynie obsługuje aplikacji, nadal potrzebowałbym klasy pochodnej, aby dodać tę operację.

Steve314
źródło
2
Nazywaj mnie szalonym, ale kiedy myślę o typie, takim jak opisujesz, służącym do stosowania i komponowania itp., Myślę o funktorach aplikacyjnych, które to funkcje. Być może to jest klasa, o której myślisz?
Jimmy Hoffa
1
Nie sądzę, że Applicativejest to całkiem słuszne - wymaga to zarówno pakowania wartości, jak i funkcji, podczas gdy chcę tylko zawijać funkcje, a funkcje zawinięte tak naprawdę są funkcjami, podczas gdy moje funkcje zawinięte zwykle nie są (w najbardziej ogólny przypadek to AST opisujące funkcje). Gdzie <*>ma typ f (a -> b) -> f a -> f b, chcę operatora aplikacji z typem g a b -> a -> bgdzie ai bokreśl domenę i kododainę zawiniętej funkcji, ale to, co jest w opakowaniu, nie jest (koniecznie) prawdziwą funkcją. Na strzały - być może, rzuci mi okiem.
Steve314,
3
jeśli chcesz odwrotnie, nie oznaczałoby to grupy?
jk.
1
@jk. świetny punkt, zdając sobie sprawę, że istnieje wiele rzeczy do przeczytania na temat odwrotności funkcji, które mogą doprowadzić OP do znalezienia tego, czego szuka. Oto kilka interesujących lektur na ten temat. Ale odwrotność funkcji haskell w Google daje wiele ciekawych treści do czytania. Być może po prostu chce Data.Group
Jimmy Hoffa
2
@ Steve314 Myślałem, że funkcje z kompozycją są kategorią monoidalną. Są monoidem, jeśli domena i domena kodowa są zawsze takie same.
Tim Seguine

Odpowiedzi:

14

Cóż, nie znam żadnych pomysłów wypiekanych na rynku jako reprezentujących rzeczy „funkcjonalne”. Ale jest kilka, które się zbliżają

Kategorie

Jeśli masz prostą koncepcję funkcji, która ma tożsamości i skład, niż masz kategorię.

class Category c where
  id :: c a a
  (.) :: c b c -> c a b -> c a c

Wadą jest to, że nie można stworzyć miłą kategorii wystąpienie z zestawem obiektów ( a, b, i c). Możesz stworzyć niestandardową klasę kategorii, jak sądzę.

Strzały

Jeśli twoje funkcje mają pojęcie o produktach i mogą wprowadzać dowolne funkcje, to strzałki są dla ciebie

 class Arrow a where
   arr :: (b -> c) -> a b c
   first :: a b c -> a (b, d) (c, d)
   second :: a b c -> a (d, b) (d, c)

ArrowApply ma pojęcie aplikacji, które wydaje się ważne dla tego, czego chcesz.

Wnioskodawcy

Wnioskodawcy mają twoje pojęcie o aplikacji, użyłem ich w AST do reprezentowania aplikacji funkcji.

class Functor f => Applicative f where
  pure :: a -> f a
  (<*>) :: f (a -> b) -> f b -> f c

Istnieje wiele innych pomysłów. Ale częstym tematem jest budowanie struktury danych reprezentującej twoją funkcję, a następnie przekazywanie jej do funkcji interpretacyjnej.

To także ile wolnych monad działa. Sugerowałbym szturchanie ich, jeśli czujesz się odważny, są one potężnym narzędziem do rzeczy, które sugerujesz, i zasadniczo pozwalają zbudować strukturę danych za pomocą donotacji, a następnie zwinąć ją do obliczeń efektów ubocznych z różnymi funkcjami . Ale piękno polega na tym, że te funkcje działają po prostu na strukturze danych i nie są tak naprawdę świadomi, jak to wszystko zrobili. Oto, co zasugerowałbym dla twojego przykładu tłumacza.

Daniel Gratzer
źródło
Wydaje się, że kategoria nie ma zastosowania ($). Strzały na pierwszy rzut oka wyglądają jak ogromne przesady, ale wciąż ArrowApplybrzmią obiecująco - tak długo, jak nie muszę niczego zapewniać, nie mogę być w porządku. +1 na chwilę, z większą ilością do sprawdzenia.
Steve314
3
@ Steve314 Kategoriom brakuje aplikacji, ale monady nie mają uniwersalnego sposobu ich uruchamiania, co nie znaczy, że nie są przydatne
Daniel Gratzer
Istnieje wspólny powód, dla którego nie mogę użyć Applicativelub Arrow(lub Monad) - nie mogę zawinąć normalnej funkcji (ogólnie), ponieważ wartości mojego typu reprezentują funkcję, ale są reprezentowane przez dane i nie będą obsługiwać funkcji arbitralnych, jeśli jeśli istniał sposób na tłumaczenie. Oznacza to, że nie mogę zapewnić pure, arrani returndla przypadków. BTW - te klasy są przydatne, ale nie mogę ich użyć do tego konkretnego celu. Arrownie jest „masywną przesadą” - to było fałszywe wrażenie po ostatniej próbie przeczytania artykułu, kiedy nie byłem gotowy go zrozumieć.
Steve314,
@ Steve314 Pomysł zapewnienia interfejsu monady do gromadzenia danych jest tym, do czego służą darmowe monady, sprawdź je
Daniel Gratzer
Obejrzałem wideo z Haskell Exchange 2013 - Andres Löh zdecydowanie to dobrze wyjaśnia, chociaż prawdopodobnie nadal muszę go obejrzeć, zagrać z techniką itp. Nie jestem jednak pewien, czy jest tu potrzebny. Moim celem jest abstrakcja funkcji przy użyciu reprezentacji, która nie jest funkcją (ale która ma funkcję interpretera). Nie potrzebuję abstrakcji efektów ubocznych i nie potrzebuję czystej notacji do operacji sekwencjonowania. Gdy abstrakcja funkcji jest w użyciu, aplikacje i kompozycje będą tworzone pojedynczo w algorytmie w innej bibliotece.
Steve314,
2

Jak zauważyłeś, głównym problemem związanym z używaniem Aplikacji jest brak rozsądnej definicji pure. Dlatego Applyzostał wynaleziony. Przynajmniej tak to rozumiem.

Niestety nie mam pod ręką przykładów takich przypadków Applyteż nie ma Applicative. Twierdzi się, że to prawda IntMap, ale nie mam pojęcia, dlaczego. Podobnie nie wiem, czy twój przykład - offset liczb całkowitych - dopuszcza Applyinstancję.

użytkownik185657
źródło
brzmi to bardziej jak komentarz, patrz Jak odpowiedzieć
komnata
Przepraszam. To mniej więcej moja pierwsza odpowiedź.
user185657
Jak sugerujesz poprawić odpowiedź?
user185657
rozważ edycję, aby pomóc czytelnikom zobaczyć, w jaki sposób twoja odpowiedź odnosi się do zadanego pytania: „dlaczego nie ma typowej dla funkcji funkcji? Czy to„ tylko dlatego, że jej nie ma ”lub„ ponieważ nie jest tak przydatna, jak myślisz ”? istnieje podstawowy problem z tym pomysłem? ”
komara
1
Mam nadzieję, że tak będzie lepiej
user185657
1

Oprócz wymienionych Category, Arroworaz Applicative:

Odkryłem również Data.Lambdaprzez Conal Elliott:

Niektóre klasy funkcjonalne, mające budowę podobną do lambda

Wygląda interesująco, ale trudno go zrozumieć bez przykładów ...

Przykłady

Przykłady można znaleźć na stronie wiki o wartościach materialnych (TV), które wydają się być jedną z rzeczy, które spowodowały utworzenie TypeComposebiblioteki; patrz Wejścia i wartościowe wartości wyjściowe .

Ideą biblioteki telewizyjnej jest wyświetlanie wartości Haskella (w tym funkcji) w namacalny sposób.

Aby postępować zgodnie z regułą StackOverflow dotyczącą nie publikowania gołych samotników, kopiuję kilka bitów poniżej, które powinny dać wyobrażenie o tych rzeczach:

Pierwszy przykład brzmi:

apples, bananas :: CInput Int
apples  = iTitle "apples"  defaultIn
bananas = iTitle "bananas" defaultIn

shoppingO :: COutput (Int -> Int -> Int)
shoppingO = oTitle "shopping list" $
            oLambda apples (oLambda bananas total)

shopping :: CTV (Int -> Int -> Int)
shopping = tv shoppingO (+)

co daje, gdy jest uruchomiony jako runIO shopping(zobacz tam więcej komentarzy, GUI i więcej przykładów):

shopping list: apples: 8
bananas: 5
total: 13
imz - Ivan Zakharyaschev
źródło
w jaki sposób rozwiązuje to pytanie? patrz Jak odpowiedzieć
komnata
@gnat Myślałem, że w definicjach podane Data.Lambdasą klasy dla rzeczy podobnych do funkcji (o które poproszono) ... Nie byłem pewien, jak te rzeczy mają być używane. Trochę to zbadałem. Prawdopodobnie nie zapewniają one jednak abstrakcji dla aplikacji funkcji.
imz - Ivan Zachharyaschev