oopfunctional-programmingabstractionnomenclaturegeneralization

What's the difference between abstraction and generalization?


I understand that abstraction is about taking something more concrete and making it more abstract. That something may be either a data structure or a procedure. For example:

  1. Data abstraction: A rectangle is an abstraction of a square. It concentrates on the fact a square has two pairs of opposite sides and it ignores the fact that adjacent sides of a square are equal.
  2. Procedural abstraction: The higher order function map is an abstraction of a procedure which performs some set of operations on a list of values to produce an entirely new list of values. It concentrates on the fact that the procedure loops through every item of the list in order to produce a new list and ignores the actual operations performed on every item of the list.

So my question is this: how is abstraction any different from generalization? I'm looking for answers primarily related to functional programming. However if there are parallels in object-oriented programming then I would like to learn about those as well.


Solution

  • Object:

    portal cake photo

    Abstraction:

    cake symbol

    Generalization:

    many desserts

    Example in Haskell:

    The implementation of the selection sort by using priority queue with three different interfaces:

    {-# LANGUAGE RankNTypes #-}
    
    module Main where
    
    import qualified Data.List as List
    import qualified Data.Set as Set
    
    {- TYPES: -}
    
    -- PQ new push pop
    -- by intention there is no build-in way to tell if the queue is empty
    data PriorityQueue q t = PQ (q t) (t -> q t -> q t) (q t -> (t, q t))
    -- there is a concrete way for a particular queue, e.g. List.null
    type ListPriorityQueue t = PriorityQueue [] t
    -- but there is no method in the abstract setting
    newtype AbstractPriorityQueue q = APQ (forall t. Ord t => PriorityQueue q t)
    
    
    {- SOLUTIONS: -}
    
    -- the basic version
    list_selection_sort :: ListPriorityQueue t -> [t] -> [t]
    list_selection_sort (PQ new push pop) list = List.unfoldr mypop (List.foldr push new list)
      where
        mypop [] = Nothing -- this is possible because we know that the queue is represented by a list
        mypop ls = Just (pop ls)
    
    
    -- here we abstract the queue, so we need to keep the queue size ourselves
    abstract_selection_sort :: Ord t => AbstractPriorityQueue q -> [t] -> [t]
    abstract_selection_sort (APQ (PQ new push pop)) list = List.unfoldr mypop (List.foldr mypush (0,new) list)
      where
        mypush t (n, q) = (n+1, push t q)
        mypop (0, q) = Nothing
        mypop (n, q) = let (t, q') = pop q in Just (t, (n-1, q'))
    
    
    -- here we generalize the first solution to all the queues that allow checking if the queue is empty
    class EmptyCheckable q where
      is_empty :: q -> Bool
    
    generalized_selection_sort :: EmptyCheckable (q t) => PriorityQueue q t -> [t] -> [t]
    generalized_selection_sort (PQ new push pop) list = List.unfoldr mypop (List.foldr push new list)
      where
        mypop q | is_empty q = Nothing
        mypop q | otherwise  = Just (pop q)
    
    
    {- EXAMPLES: -}
    
    -- priority queue based on lists
    priority_queue_1 :: Ord t => ListPriorityQueue t
    priority_queue_1 = PQ [] List.insert (\ls -> (head ls, tail ls))
    instance EmptyCheckable [t] where
      is_empty = List.null
    
    -- priority queue based on sets
    priority_queue_2 :: Ord t => PriorityQueue Set.Set t
    priority_queue_2 = PQ Set.empty Set.insert Set.deleteFindMin
    instance EmptyCheckable (Set.Set t) where
      is_empty = Set.null
    
    -- an arbitrary type and a queue specially designed for it
    data ABC = A | B | C deriving (Eq, Ord, Show)
    
    -- priority queue based on counting
    data PQ3 t = PQ3 Integer Integer Integer
    priority_queue_3 :: PriorityQueue PQ3 ABC
    priority_queue_3 = PQ new push pop
      where
        new = (PQ3 0 0 0)
        push A (PQ3 a b c) = (PQ3 (a+1) b c)
        push B (PQ3 a b c) = (PQ3 a (b+1) c)
        push C (PQ3 a b c) = (PQ3 a b (c+1))
        pop (PQ3 0 0 0) = undefined
        pop (PQ3 0 0 c) = (C, (PQ3 0 0 (c-1)))
        pop (PQ3 0 b c) = (B, (PQ3 0 (b-1) c))
        pop (PQ3 a b c) = (A, (PQ3 (a-1) b c))
    
    instance EmptyCheckable (PQ3 t) where
      is_empty (PQ3 0 0 0) = True
      is_empty _ = False
    
    
    {- MAIN: -}
    
    main :: IO ()
    main = do
      print $ list_selection_sort priority_queue_1 [2, 3, 1]
      -- print $ list_selection_sort priority_queue_2 [2, 3, 1] -- fail
      -- print $ list_selection_sort priority_queue_3 [B, C, A] -- fail
      print $ abstract_selection_sort (APQ priority_queue_1) [B, C, A] -- APQ hides the queue 
      print $ abstract_selection_sort (APQ priority_queue_2) [B, C, A] -- behind the layer of abstraction
      -- print $ abstract_selection_sort (APQ priority_queue_3) [B, C, A] -- fail
      print $ generalized_selection_sort priority_queue_1 [2, 3, 1]
      print $ generalized_selection_sort priority_queue_2 [B, C, A]
      print $ generalized_selection_sort priority_queue_3 [B, C, A]-- power of generalization
    
      -- fail
      -- print $ let f q = (list_selection_sort q [2,3,1], list_selection_sort q [B,C,A])
      --         in f priority_queue_1
    
      -- power of abstraction (rank-n-types actually, but never mind)
      print $ let f q = (abstract_selection_sort q [2,3,1], abstract_selection_sort q [B,C,A]) 
              in f (APQ priority_queue_1)
    
      -- fail
      -- print $ let f q = (generalized_selection_sort q [2,3,1], generalized_selection_sort q [B,C,A])
      --         in f priority_queue_1
    

    The code is also available via pastebin.

    Worth noticing are the existential types. As @lukstafi already pointed out, abstraction is similar to existential quantifier and generalization is similar to universal quantifier. Observe that there is a non-trivial connection between the fact that ∀x.P(x) implies ∃x.P(x) (in a non-empty universe), and that there rarely is a generalization without abstraction (even c++-like overloaded functions form a kind of abstraction in some sense).

    Credits: Portal cake by Solo. Dessert table by djttwo. The symbol is the cake icon from material.io.