Skip to content

Instantly share code, notes, and snippets.

@xiaohanyu

xiaohanyu/powerset-in-haskell-and-python.org

Created March 6, 2017 15:08
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save xiaohanyu/384c93892f781af1dc6524380725c780 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save xiaohanyu/384c93892f781af1dc6524380725c780 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. xiaohanyu created this gist Mar 6, 2017.
    31 changes: 31 additions & 0 deletions powerset-in-haskell-and-python.org
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,31 @@
    Here're two powerset function implemented in Python and Haskell.

    #+BEGIN_SRC python :tangle powerset.py
    import copy

    def powerset(s):
    if s == []:
    return [[]]
    elif len(s) == 1:
    return [[], s]
    else:
    powerset1 = powerset(s[1:])
    powerset2 = []
    for ss in powerset1:
    new_ss = copy.deepcopy(ss)
    new_ss.insert(0, s[0])
    powerset2.append(new_ss)

    return powerset1 + powerset2
    #+END_SRC

    #+BEGIN_SRC haskell :tangle powerset.hs
    powerset :: [a] -> [[a]]
    powerset [] = [[]]
    powerset [x] = [[], [x]]
    powerset (x:xs) = [x:px | px <- powerset(xs)] ++ powerset(xs)
    #+END_SRC

    And we can see that in a language with [[https://en.wikipedia.org/wiki/Pattern_matching][Pattern matching]], [[https://en.wikipedia.org/wiki/Lazy_evaluation][Lazy evaluation]] and
    immutable data structures like Haskell, it's really easy and elegant to
    implement some mathematical functions.