问题描述
我理解抽象就是将一些更具体的东西变得更抽象.那个东西可能是一个数据结构或一个过程.例如:
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:
- 数据抽象:矩形是正方形的抽象.它专注于正方形有两对对边这一事实,而忽略了正方形相邻边相等的事实.
- 过程抽象:高阶函数
map
是一个过程的抽象,它对值列表执行一些操作以产生一个全新的值列表.它专注于这样一个事实,即该过程循环遍历列表的每个项目以生成一个新列表,并忽略对列表的每个项目执行的实际操作.
- 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.
- 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.
推荐答案
对象:
抽象:
概括:
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
该代码也可通过 pastebin 获得.
The code is also available via pastebin.
值得注意的是存在类型.正如@lukstafi 已经指出的那样,抽象类似于存在量词,泛化类似于全称量词.观察到 ∀xP(x) 蕴涵 ∃xP(x)(在非空宇宙中)与很少有没有抽象的泛化(即使是类似 c++ 的重载函数形式)之间存在重要的联系某种意义上的一种抽象).
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).
信用:Solo 的门户蛋糕.djttwo 的甜点表.该符号是来自 material.io 的蛋糕图标.
Credits:Portal cake by Solo.Dessert table by djttwo.The symbol is the cake icon from material.io.
这篇关于抽象和概括有什么区别?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!