本文介绍了什么是“总和与积"?数据结构?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

  • 数据类型代数快速介绍,http://blog.lab49.com/archives/3011 (链接似乎已失效.互联网档案链接:http://web-old.archive.org/web/20120321033340/http://blog.lab49.com/archives/3011)
  • 物种、函子和类型,天哪!,Brent Yorgey,http://www.cis.upenn.edu/~byorgey/papers/species-pearl.pdf -- 对代数、Haskell 数据类型以及与组合物种的联系有很好的概述来自数学.
  • A recent blog post on William Cook's Fusings mentions:

    What are the traditional sums-and-products data structures he is referring to?

    解决方案

    In type theory, regular data structures can be described in terms of sums, products and recursive types. This leads to an algebra for describing data structures (and so-called algebraic data types). Such data types are common in statically typed functional languages, such as ML or Haskell.

    Products

    Products can be thought of as the type-theoretic view of "structs" or "tuples".

    Formally, PFPL, Ch 14:

    Sums

    Sum types express choice between variants of a data structure. Sometimes they are called "union types" (as in C). Many languages have no notion of sum types.

    PFPL, ch 15:

    Recursive types

    Along with products and sums, we can introduce recursion, so a type may be defined (partially) in terms of itself. Nice examples include trees and lists.

     data List a = Empty | a : List a
    
     data Tree a = Nil | Node a (Tree a) (Tree a)
    

    Algebra of sums, products and recursion

    Give a type, say Int, we can start building up a notation for algebraic expressions that describe data structures:

    A lone variable:

    Int

    A product of two types (denoting a pair):

    Int * Bool

    A sum of two types (denoting a choice between two types):

    Int + Bool

    And some constants:

    1 + Int

    where 1 is the unit type, ().

    Once you can describe types this way, you get some cool power for free. Firstly, a very concise notation for describing data types, secondly, some results transfer from other algebras (e.g. differentiation works on data structures).

    Examples

    The unit type, data () = ()

    A tuple, the simplest product type: data (a,b) = (a,b)

    A simple sum type, data Maybe a = Nothing | Just a

    and its alternative,

    and a recursive type, the type of linked lists: data [a] = [] | a : [a]

    Given these, you can build quite complicated structures by combining sums, products and recursive types.E.g. the simple notation for a list of products of sums of products: [(Maybe ([Char], Double), Integer)] gives rise to some quite complicated trees:


    References

    这篇关于什么是“总和与积"?数据结构?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

    07-16 13:19
    查看更多