Jak nazywa się argument funkcjonalny w fold

10

W funkcji wyższego rzędu zwiń / zmniejsz, jaka jest nazwa ewentualnego argumentu funkcjonalnego?

Pracuję nad monadyczną tabelaryczną biblioteką przetwarzania, w której wiersze są składane w celu uzyskania prostych analiz (takich jak znalezienie minimalnej, maksymalnej, średniej kolumny). Dlatego szukam solidnej nazwy dla argumentu foldfunkcji i każda nazwa, która jest dobrze ugruntowana w społeczności ML (lub Haskell lub Common Lisp jako drugi i trzeci kandydat) byłaby interesująca.

Nazwa podobna fjest powszechna w opisie foldfunkcji, jest jednak nieopisowa i rzeczownik lepiej by pasował.

użytkownik40989
źródło
10
Nie ma jednego W rzeczywistości nie ma nawet powszechnie używanej nazwy dla katamorfizmów (fold)
Daniel Gratzer
2
Jeśli jest to pytanie dotyczące zadania szkolnego lub egzaminu, musisz uzyskać odpowiedź od nauczyciela lub podręcznika, a nie od nas. Może nazywa to czymś innym. To, czego uczy się w klasie, nie zawsze jest tym, co jest powszechnie stosowane w prawdziwym świecie.
Robert Harvey
7
@RobertHarvey To nie jest pytanie egzaminacyjne (?) Ani nic podobnego. Jako programista uważam, że wybór dobrych nazw dla obiektów programistycznych (typów, zmiennych itp.) Jest bardzo ważny. A jeśli coś ma dobrze znaną nazwę, to nie ma powodu, aby jej nie używać - oprócz ignorancji, i po to są pytania.
user40989,
9
@Izkata Nie, to nieprawda. Funkcja wyższego rzędu jest funkcją, która przyjmuje funkcję. foldjest funkcją wyższego rzędu. Argument do spasowania jest po prostu tym, argumentem
Daniel Gratzer
1
@ jozefg To jako odpowiedź na drugą część twojego komentarza. Jeśli chodzi o pierwszą część (i pytanie), zobacz mój post na Meta. Nazywa się je parametrami proceduralnymi.
Izkata,

Odpowiedzi:

8

Nie wiem, czy jest na to jakaś odpowiedź, jak wspomniał @jozefg. I tak wyłącznie z powodu spekulacji, oto jedno możliwe wytłumaczenie:

Podejrzewam, że powodem jest to, ponieważ typ - (a -> b -> b)w Haskell użytkownikafoldr , na przykład - jest bardziej sensowne niż jedna nazwa mogłaby wymyślić. Ponieważ parametry typu ai bmogą być dowolne , funkcja może zrobić prawie wszystko. Więc jesteś w lewo o nazwach takich jak function, combiner, morphism, i argument, które nie są szczególnie znaczące albo. Może także użyć krótkiej, nie rozpraszającej uwagi nazwy.

Innym przykładem jest id :: a -> afunkcja: jak nazwać jej argument? Ponownie myślę id, że typ jest bardziej opisowy niż nazwa argumentu.

Zgadzam się jednak z tobą - wydaje się, że powinna istnieć wspólna nazwa, być może w matematyce. Mam nadzieję, że ktoś może mnie poprawić.


Kilka przykładów jego nazwy w prawdziwym kodzie:

W bibliotekach Haskella jest to najczęściej nazywane f(a czasem operatorw komentarzach):

class Foldable t where
    -- | Map each element of the structure to a monoid,
    -- and combine the results.
    foldMap :: Monoid m => (a -> m) -> t a -> m
    foldMap f = foldr (mappend . f) mempty

    -- | Right-associative fold of a structure.
    --
    -- @'foldr' f z = 'Prelude.foldr' f z . 'toList'@
    foldr :: (a -> b -> b) -> b -> t a -> b
    foldr f z t = appEndo (foldMap (Endo . f) t) z

    -- | Right-associative fold of a structure, 
    -- but with strict application of the operator.
    foldr' :: (a -> b -> b) -> b -> t a -> b
    foldr' f z0 xs = foldl f' id xs z0
      where f' k x z = k $! f x z

    -- | Left-associative fold of a structure.
    --
    -- @'foldl' f z = 'Prelude.foldl' f z . 'toList'@
    foldl :: (a -> b -> a) -> a -> t b -> a
    foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z

    -- | Left-associative fold of a structure.
    -- but with strict application of the operator.
    --
    -- @'foldl' f z = 'List.foldl'' f z . 'toList'@
    foldl' :: (a -> b -> a) -> a -> t b -> a
    foldl' f z0 xs = foldr f' id xs z0
      where f' x k z = k $! f z x

    -- | A variant of 'foldr' that has no base case,
    -- and thus may only be applied to non-empty structures.
    --
    -- @'foldr1' f = 'Prelude.foldr1' f . 'toList'@
    foldr1 :: (a -> a -> a) -> t a -> a
    foldr1 f xs = fromMaybe (error "foldr1: empty structure")
                    (foldr mf Nothing xs)
      where
        mf x Nothing = Just x
        mf x (Just y) = Just (f x y)

    -- | A variant of 'foldl' that has no base case,
    -- and thus may only be applied to non-empty structures.
    --
    -- @'foldl1' f = 'Prelude.foldl1' f . 'toList'@
    foldl1 :: (a -> a -> a) -> t a -> a
    foldl1 f xs = fromMaybe (error "foldl1: empty structure")
                    (foldl mf Nothing xs)
      where
        mf Nothing y = Just y
        mf (Just x) y = Just (f x y)

-- instances for Prelude types

instance Foldable Maybe where
    foldr _ z Nothing = z
    foldr f z (Just x) = f x z

    foldl _ z Nothing = z
    foldl f z (Just x) = f z x

instance Ix i => Foldable (Array i) where
    foldr f z = Prelude.foldr f z . elems
    foldl f z = Prelude.foldl f z . elems
    foldr1 f = Prelude.foldr1 f . elems
    foldl1 f = Prelude.foldl1 f . elems

-- | Monadic fold over the elements of a structure,
-- associating to the right, i.e. from right to left.
foldrM :: (Foldable t, Monad m) => (a -> b -> m b) -> b -> t a -> m b
foldrM f z0 xs = foldl f' return xs z0
  where f' k x z = f x z >>= k

-- | Monadic fold over the elements of a structure,
-- associating to the left, i.e. from left to right.
foldlM :: (Foldable t, Monad m) => (a -> b -> m a) -> a -> t b -> m a
foldlM f z0 xs = foldr f' return xs z0
  where f' x k z = f z x >>= k

-- | Map each element of a structure to an action, evaluate
-- these actions from left to right, and ignore the results.
traverse_ :: (Foldable t, Applicative f) => (a -> f b) -> t a -> f ()
traverse_ f = foldr ((*>) . f) (pure ())

-- | Map each element of a structure to a monadic action, evaluate
-- these actions from left to right, and ignore the results.
mapM_ :: (Foldable t, Monad m) => (a -> m b) -> t a -> m ()
mapM_ f = foldr ((>>) . f) (return ())

Jest również nazywany f w Clojure :

(def
    ^{:arglists '([f coll] [f val coll])
      :doc "f should be a function of 2 arguments. If val is not supplied,
  returns the result of applying f to the first 2 items in coll, then
  applying f to that result and the 3rd item, etc. If coll contains no
  items, f must accept no arguments as well, and reduce returns the
  result of calling f with no arguments.  If coll has only 1 item, it
  is returned and f is not called.  If val is supplied, returns the
  result of applying f to val and the first item in coll, then
  applying f to that result and the 2nd item, etc. If coll contains no
  items, returns val and f is not called."
      :added "1.0"}    
    reduce
     (fn r
       ([f coll]
             (let [s (seq coll)]
               (if s
                 (r f (first s) (next s))
                 (f))))
       ([f val coll]
          (let [s (seq coll)]
            (if s
              (if (chunked-seq? s)
                (recur f 
                       (.reduce (chunk-first s) f val)
                       (chunk-next s))
                (recur f (f val (first s)) (next s)))
              val)))))

źródło
6

Nie zgadzam się z ideą, która fjest złą nazwą argumentu funkcji fold. Powodem, dla którego chcemy opisowych nazw w programowaniu jest to, że wiemy, co opisuje nazwa, a nazwa fjest powszechnie używana w matematyce (i funkcjonalnych językach programowania) dla funkcji (jak są gi h).

Nie wiemy prawie nic f(z założenia, ponieważ jeśli moglibyśmy być bardziej konkretni, nie moglibyśmy użyć foldna tak wielu rzeczach), a nazwa fmówi nam wszystko, co musimy wiedzieć, z wyjątkiem tego, że jest to funkcja dwóch argumentów. Nazwa fjest bardzo podobna do zaimka „it” w języku angielskim - jest symbolem zastępczym, który może znaczyć prawie wszystko. Nie wiemy, co to jest, dopóki nie użyjemy go w zdaniu, i nie wiemy, co to fjest, dopóki nie zadzwonimy fold.

Nazywając rzeczy, chcemy uzyskać jak najwięcej informacji z nazwy i wolimy, aby nazwa była krótka (jeśli możemy to uzyskać bez poświęcania ważnych informacji). Tutaj mamy bardzo krótką nazwę, która mówi nam prawie wszystko, co wiemy na ten temat. Nie sądzę, że można to poprawić.

W programowaniu imperatywnym ijest używany jako licznik pętli (jak są ji k, jeśli potrzebujemy więcej); w programowaniu funkcjonalnym fjest używany jako argument funkcji w funkcjach wyższego rzędu (jak są gi h, jeśli potrzebujemy więcej). Nie mam wystarczającego doświadczenia z językami funkcjonalnymi, aby mieć pewność, że konwencja f / g / h jest równie dobrze rozwinięta, jak konwencja i / j / k, ale jeśli tak nie jest, myślę, że powinna (zdecydowanie jest ustanowiony w matematyce).

Michael Shaw
źródło
3

Najczęstszą nazwą tego, którą słyszałem inną niż zaimek f, jest binary operationlub binary function- problem z byciem bardziej konkretnym niż to, że może zrobić dosłownie wszystko , i dlatego ludzie trzymają się podpisu typu a -> b -> a(lub a -> b -> bjeśli jest to prawidłowa fałda) .

Proponuję więc, abyś zrobił to dokładnie, trzymaj się podpisu typu, na szczęście ten podpis określonego typu ma nazwę binary function:, podobnie jak a -> ajest unary operationi a -> bjest unary function, możesz wywołać a -> a -> aa binary operationi a -> b -> ca binary function.

Jimmy Hoffa
źródło
1
Dla mnie binary operationbardziej znaczyłoby a -> a -> ai binary functionoznaczałoby a -> b -> c… prawda z pewnością leży pomiędzy. :-)
user40989,
@ user40989 dobre połączenie, poprawione.
Jimmy Hoffa
1

Funkcja, o którą prosisz, jest czasami nazywana „funkcją łączącą” (patrz np . Strona HaskellWiki w folderze ), ale nie jest to wystarczająco powszechne, aby nazwać ją standardową terminologią.

Dominique Devriese
źródło