<rt id="bn8ez"></rt>
<label id="bn8ez"></label>

  • <span id="bn8ez"></span>

    <label id="bn8ez"><meter id="bn8ez"></meter></label>

    posts - 403, comments - 310, trackbacks - 0, articles - 7
      BlogJava :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理

    【轉載】Python 中的函數式編程 (1)

    Posted on 2007-11-23 21:15 ZelluX 閱讀(1325) 評論(0)  編輯  收藏 所屬分類: Scripting
     from IBM developerWorks  原文的代碼部分很亂,整理了一下

    Although users usually think of Python as a procedural and object-oriented language, it actually contains everything you need for a completely functional approach to programming. This article discusses general concepts of functional programming, and illustrates ways of implementing functional techniques in Python.

    We'd better start with the hardest question: "What is functional programming (FP), anyway?" One answer would be to say that FP is what you do when you program in languages like Lisp, Scheme, Haskell, ML, OCAML, Clean, Mercury, or Erlang (or a few others). That is a safe answer, but not one that clarifies very much. Unfortunately, it is hard to get a consistent opinion on just what FP is, even from functional programmers themselves. A story about elephants and blind men seems apropos here. It is also safe to contrast FP with "imperative programming" (what you do in languages like C, Pascal, C++, Java, Perl, Awk, TCL, and most others, at least for the most part).

    Personally, I would roughly characterize functional programming as having at least several of the following characteristics. Languages that get called functional make these things easy, and make other things either hard or impossible:

    • Functions are first class (objects). That is, everything you can do with "data" can be done with functions themselves (such as passing a function to another function).
    • Recursion is used as a primary control structure. In some languages, no other "loop" construct exists.
    • There is a focus on LISt Processing (for example, the name Lisp). Lists are often used with recursion on sub-lists as a substitute for loops.
    • "Pure" functional languages eschew side-effects. This excludes the almost ubiquitous pattern in imperative languages of assigning first one, then another value to the same variable to track the program state.
    • FP either discourages or outright disallows statements, and instead works with the evaluation of expressions (in other words, functions plus arguments). In the pure case, one program is one expression (plus supporting definitions).
    • FP worries about what is to be computed rather than how it is to be computed.
    • Much FP utilizes "higher order" functions (in other words, functions that operate on functions that operate on functions).

    Advocates of functional programming argue that all these characteristic make for more rapidly developed, shorter, and less bug-prone code. Moreover, high theorists of computer science, logic, and math find it a lot easier to prove formal properties of functional languages and programs than of imperative languages and programs.

     

    Inherent Python functional capabilities

    Python has had most of the characteristics of FP listed above since Python 1.0. But as with most Python features, they have been present in a very mixed language. Much as with Python's OOP features, you can use what you want and ignore the rest (until you need it later). With Python 2.0, a very nice bit of "syntactic sugar" was added with list comprehensions. While list comprehensions add no new capability, they make a lot of the old capabilities look a lot nicer.

    The basic elements of FP in Python are the functions map(), reduce(), and filter(), and the operator lambda. In Python 1.x, the apply() function also comes in handy for direct application of one function's list return value to another function. Python 2.0 provides an improved syntax for this purpose. Perhaps surprisingly, these very few functions (and the basic operators) are almost sufficient to write any Python program; specifically, the flow control statements (if, elif, else, assert, try, except, finally, for, break, continue, while, def) can all be handled in a functional style using exclusively the FP functions and operators. While actually eliminating all flow control commands in a program is probably only useful for entering an "obfuscated Python" contest (with code that will look a lot like Lisp), it is worth understanding how FP expresses flow control with functions and recursion.

     

    We'd better start with the hardest question: "What is functional programming (FP), anyway?" One answer would be to say that FP is what you do when you program in languages like Lisp, Scheme, Haskell, ML, OCAML, Clean, Mercury, or Erlang (or a few others). That is a safe answer, but not one that clarifies very much. Unfortunately, it is hard to get a consistent opinion on just what FP is, even from functional programmers themselves. A story about elephants and blind men seems apropos here. It is also safe to contrast FP with "imperative programming" (what you do in languages like C, Pascal, C++, Java, Perl, Awk, TCL, and most others, at least for the most part).

    Personally, I would roughly characterize functional programming as having at least several of the following characteristics. Languages that get called functional make these things easy, and make other things either hard or impossible:

    • Functions are first class (objects). That is, everything you can do with "data" can be done with functions themselves (such as passing a function to another function).
    • Recursion is used as a primary control structure. In some languages, no other "loop" construct exists.
    • There is a focus on LISt Processing (for example, the name Lisp). Lists are often used with recursion on sub-lists as a substitute for loops.
    • "Pure" functional languages eschew side-effects. This excludes the almost ubiquitous pattern in imperative languages of assigning first one, then another value to the same variable to track the program state.
    • FP either discourages or outright disallows statements, and instead works with the evaluation of expressions (in other words, functions plus arguments). In the pure case, one program is one expression (plus supporting definitions).
    • FP worries about what is to be computed rather than how it is to be computed.
    • Much FP utilizes "higher order" functions (in other words, functions that operate on functions that operate on functions).

    Advocates of functional programming argue that all these characteristic make for more rapidly developed, shorter, and less bug-prone code. Moreover, high theorists of computer science, logic, and math find it a lot easier to prove formal properties of functional languages and programs than of imperative languages and programs.

    Inherent Python functional capabilities

    Python has had most of the characteristics of FP listed above since Python 1.0. But as with most Python features, they have been present in a very mixed language. Much as with Python's OOP features, you can use what you want and ignore the rest (until you need it later). With Python 2.0, a very nice bit of "syntactic sugar" was added with list comprehensions. While list comprehensions add no new capability, they make a lot of the old capabilities look a lot nicer.

    The basic elements of FP in Python are the functions map(), reduce(), and filter(), and the operator lambda. In Python 1.x, the apply() function also comes in handy for direct application of one function's list return value to another function. Python 2.0 provides an improved syntax for this purpose. Perhaps surprisingly, these very few functions (and the basic operators) are almost sufficient to write any Python program; specifically, the flow control statements (if, elif, else, assert, try, except, finally, for, break, continue, while, def) can all be handled in a functional style using exclusively the FP functions and operators. While actually eliminating all flow control commands in a program is probably only useful for entering an "obfuscated Python" contest (with code that will look a lot like Lisp), it is worth understanding how FP expresses flow control with functions and recursion.


    Eliminating flow control statements

    The first thing to think about in our elimination exercise is the fact that Python "short circuits" evaluation of Boolean expressions. This provides an expression version of if/ elif/ else blocks (assuming each block calls one function, which is always possible to arrange). Here's how:

    Listing 1. "Short-circuit" conditional calls in Python

    # Normal statement-based flow control 
    if <cond1>
        func1() 
    elif <cond2>
        func2() 
    else
        func3() 

    # Equivalent "short circuit" expression 
    (<cond1> and func1()) or (<cond2> and func2()) or (func3()) 

    # Example "short circuit" expression 
    >>> x = 3 
    >>> def pr(s): 
            
    return s 
    >>> (x==1 and pr('one')) or (x==2 and pr('two')) or (pr('other')) 
    'other' 
    >>> x = 2 
    >>> (x==1 and pr('one')) or (x==2 and pr('two')) or (pr('other')) 
    'two' 

    Our expression version of conditional calls might seem to be nothing but a parlor trick; however, it is more interesting when we notice that the lambda operator must return an expression. Since -- as we have shown -- expressions can contain conditional blocks via short-circuiting, a lambda expression is fully general in expressing conditional return values. Building on our example:

    Listing 2. Lambda with short-circuiting in Python

    >>> pr = lambda s:s 
    >>> namenum = lambda x: (x==1 and pr("one")) \ 
    or (x==2 and pr("two")) \ 
    or (pr("other")) 
    >>> namenum(1
    'one' 
    >>> namenum(2
    'two' >>> namenum(3'other' 


    Functions as first class objects

    The above examples have already shown the first class status of functions in Python, but in a subtle way. When we create a function object with the lambda operation, we have something entirely general. As such, we were able to bind our objects to the names "pr" and "namenum", in exactly the same way we might have bound the number 23 or the string "spam" to those names. But just as we can use the number 23 without binding it to any name (in other words, as a function argument), we can use the function object we created with lambda without binding it to any name. A function is simply another value we might do something with in Python.

    The main thing we do with our first class objects, is pass them to our FP built-in functions map(), reduce(), and filter(). Each of these functions accepts a function object as its first argument.

    • map() performs the passed function on each corresponding item in the specified list(s), and returns a list of results.
    • reduce() performs the passed function on each subsequent item and an internal accumulator of a final result; for example, reduce(lambda n,m:n*m, range(1,10)) means "factorial of 10" (in other words, multiply each item by the product of previous multiplications).
    • filter() uses the passed function to "evaluate" each item in a list, and return a winnowed list of the items that pass the function test.

     

    We also often pass function objects to our own custom functions, but usually those amount to combinations of the mentioned built-ins.

    By combining these three FP built-in functions, a surprising range of "flow" operations can be performed (all without statements, only expressions).



    Functional looping in Python

    Replacing loops is as simple as was replacing conditional blocks. for can be directly translated to map(). As with our conditional execution, we will need to simplify statement blocks to single function calls (we are getting close to being able to do this generally):

    for e in lst: func(e)       statement-based loop
    map(func,lst)      # map()-based loop      

    By the way, a similar technique is available for a functional approach to sequential program flow. That is, imperative programming mostly consists of statements that amount to "do this, then do that, then do the other thing." map() lets us do just this:

    # let's create an execution utility function
       do_it = lambda f: f()
    # let f1, f2, f3 (etc) be functions that perform actions
       map(do_it, [f1,f2,f3])   # map()-based action sequence  

    In general, the whole of our main program can be a map() expression with a list of functions to execute to complete the program. Another handy feature of first class functions is that you can put them in a list.

    Translating while is slightly more complicated, but is still possible to do directly:

    Listing 5. Functional 'while' looping in Python

     

    # statement-based while loop
    while <cond>:
        
    <pre-suite>
        
    if <break_condition>:
            
    break
        
    else:
            
    <suite>   

    # FP-style recursive while loopp
    def while_block():
        
    <pre-suite>
        
    if <break_condition>:
            
    return 1
        
    else:
            
    <suite>
            
    return 0

    while_FP 
    = lambda: (<cond> and while_block()) or while_FP()
    while_FP()

     

    Our translation of while still requires a while_block() function that may itself contain statements rather than just expressions. But we might be able to apply further eliminations to that function (such as short circuiting the if/else in the template). Also, it is hard for <cond> to be useful with the usual tests, such as while myvar==7, since the loop body (by design) cannot change any variable values (well, globals could be modified in while_block()). One way to add a more useful condition is to let while_block() return a more interesting value, and compare that return for a termination condition. It is worth looking at a concrete example of eliminating statements:

    Listing 6. Functional 'echo' loop in Python

    # imperative version of "echo()" 
    def echo_IMP(): 
        
    while 1
            x 
    = raw_input("IMP -- "
            
    if x == 'quit'
                
    break 
            
    else 
                
    print x 
            echo_IMP() 

    # utility function for "identity with side-effect" 
    def monadic_print(x): 
        
    print x 
        
    return x 

    # FP version of "echo()" 
    echo_FP = lambda: monadic_print(raw_input("FP -- "))=='quit' or echo_FP() 
    echo_FP() 

     

    What we have accomplished is that we have managed to express a little program that involves I/O, looping, and conditional statements as a pure expression with recursion (in fact, as a function object that can be passed elsewhere if desired). We do still utilize the utility function monadic_print(), but this function is completely general, and can be reused in every functional program expression we might create later (it's a one-time cost). Notice that any expression containing monadic_print(x) evaluates to the same thing as if it had simply contained x. FP (particularly Haskell) has the notion of a "monad" for a function that "does nothing, and has a side-effect in the process."



    Eliminating side-effects

    After all this work in getting rid of perfectly sensible statements and substituting obscure nested expressions for them, a natural question is "Why?!" All of my descriptions of FP are achieved in Python. But the most important characteristic -- and the one likely to be concretely useful -- is the elimination of side-effects (or at least their containment to special areas like monads). A very large percentage of program errors -- and the problem that drives programmers to debuggers -- occur because variables obtain unexpected values during the course of program execution. Functional programs bypass this particular issue by simply not assigning values to variables at all.

    Let's look at a fairly ordinary bit of imperative code. The goal here is to print out a list of pairs of numbers whose product is more than 25. The numbers that make up the pairs are themselves taken from two other lists. This sort of thing is moderately similar to things that programmers actually do in segments of their programs. An imperative approach to the goal might look like:

    Listing 7. Imperative Python code for "print big products"

    # Nested loop procedural style for finding big products 
    xs = (1,2,3,4
    ys 
    = (10,15,3,22
    bigmuls 
    = [] 
    # more stuff 
    for x in xs: 
        
    for y in ys: 
            
    # more stuff 
            if x*> 25: bigmuls.append((x,y)) 
            
    # more stuff 

    # more stuff 
    print bigmuls 

     

    This project is small enough that nothing is likely to go wrong. But perhaps our goal is embedded in code that accomplishes a number of other goals at the same time. The sections commented with "more stuff" are the places where side-effects are likely to lead to bugs. At any of these points, the variables xs, ys, bigmuls, x, y might acquire unexpected values in the hypothetical abbreviated code. Furthermore, after this bit of code is done, all the variables have values that may or may not be expected and wanted by later code. Obviously, encapsulation in functions/instances and care regarding scope can be used to guard against this type of error. And you can always del your variables when you are done with them. But in practice, the types of errors indicated are common.

    A functional approach to our goal eliminates these side-effect errors altogether. A possible bit of code is:

    bigmuls = lambda xs,ys: filter(lambda (x,y):x*> 25, combine(xs,ys))
    combine 
    = lambda xs,ys: map(None, xs*len(ys), dupelms(ys,len(xs)))
    dupelms 
    = lambda lst,n: reduce(lambda s,t:s+t, map(lambda l,n=n: [l]*n, lst))
    print bigmuls((1,2,3,4),(10,15,3,22))

    We bind our anonymous (lambda) function objects to names in the example, but that is not strictly necessary. We could instead simply nest the definitions. For readability we do it this way; but also because combine() is a nice utility function to have anyway (produces a list of all pairs of elements from two input lists). dupelms() in turn is mostly just a way of helping out combine(). Even though this functional example is more verbose than the imperative example, once you consider the utility functions for reuse, the new code in bigmuls() itself is probably slightly less than in the imperative version.

    The real advantage of this functional example is that absolutely no variables change any values within it. There are no possible unanticipated side-effects on later code (or from earlier code). Obviously, the lack of side-effects, in itself, does not guarantee that the code is correct, but it is nonetheless an advantage. Notice, however, that Python (unlike many functional languages) does not prevent rebinding of the names bigmuls, combine and dupelms. If combine() starts meaning something different later in the program, all bets are off. You could work up a Singleton class to contain this type of immutable bindings (as, say, s.bigmuls and so on); but this column does not have room for that.

    One thing distinctly worth noticing is that our particular goal is tailor-made for a new feature of Python 2. Rather than either the imperative or functional examples given, the best (and functional) technique is:

    print [(x,y) for x in (1,2,3,4for y in (10,15,3,22if x*> 25]




    Closure

    I've shown ways to replace just about every Python flow-control construct with a functional equivalent (sparing side-effects in the process). Translating a particular program efficiently takes some additional thinking, but we have seen that the functional built-ins are general and complete. In later columns, we will look at more advanced techniques for functional programming; and hopefully we will be able to explore some more of the pros and cons of functional styles.



    Resources



    About the author

     

    Since conceptions without intuitions are empty, and intuitions without conceptions, blind, David Mertz wants a cast sculpture of Milton for his office. Start planning for his birthday. David may be reached at mertz@gnosis.cx; his life pored over at http://gnosis.cx/dW/. Suggestions and recommendations on this, past, or future, columns are welcomed.

    主站蜘蛛池模板: 真人做A免费观看| 亚洲成?Ⅴ人在线观看无码| 亚洲最大福利视频| 国产一区视频在线免费观看| 国产高清对白在线观看免费91| 久热综合在线亚洲精品| 成人午夜性A级毛片免费| 一边摸一边爽一边叫床免费视频| 亚洲精品自产拍在线观看动漫| 久久久久久99av无码免费网站| 一级做a爰黑人又硬又粗免费看51社区国产精品视 | 99视频在线精品免费| 亚洲av永久无码精品网址| 亚洲国产精品成人精品无码区 | 亚洲美女免费视频| 婷婷亚洲天堂影院| 免费播放一区二区三区| 精品亚洲视频在线| 亚洲高清免费在线观看| 亚洲日韩国产精品乱| 成人爽A毛片免费看| 13小箩利洗澡无码视频网站免费| 国产精品亚洲精品观看不卡| 伊人久久大香线蕉亚洲| 免费毛片在线播放| 最近免费中文在线视频| 国产精品免费αv视频| 亚洲人成色77777在线观看| 亚洲国产精久久久久久久| 亚洲 国产 图片| 成人黄动漫画免费网站视频| 日本不卡免费新一区二区三区| 在线亚洲v日韩v| 亚洲粉嫩美白在线| 久久久亚洲欧洲日产国码是AV| 亚洲精品人成无码中文毛片| 成人免费看吃奶视频网站| 最近中文字幕无免费| 国产在线观看免费av站| 国产成人亚洲精品91专区高清| 久久综合久久综合亚洲|