[프로그래밍언어론] 과제 3 : 함수형 프로그래밍 (Functional Programming)

문제

이미 제출한 대다수의 학생이 Functional Programming의 원칙(No variables and assignments, No statements, No side-effects, Referential transparency)을 준수하지 않는 답안을 제출하였습니다. Functional Programming을 제대로 구사하려면 식과 값만 사용하여 프로그래밍 해야합니다. 이런 사고에 익숙해져야 다른 언어를 사용하더라도 함수형 프로그래밍의 장점을 살릴 수 있습니다. 앞에서도 언급했지만 이번에 과제로 나간 문제들은fold(reduce, foldr, foldl)를 사용하여 하나의 식으로 풀 수 있는 문제들입니다.  현재까지 단 한명의 학생만이 이런 취지에 매우 근접한 해답을 제출하였습니다.

 

Code the following functions in functional style. You may use any language you like, but you might have to choose one which supports data structures given in the problem set (e.g. lists). Use higher-order functions such as map, filter, and fold(reduce, foldr, foldl) whenever possible.You may also define auxiliary functions to solve the given problems.

 

(Each problem can be solved with only 1-expression using fold and lambdas.)

The examples are given following the Scheme syntax for convenience’s sake.

 

(count x l) counts the number of occurrences of x at the top level of l, and (countall x l) counts the number of occurrences throughout l.

• (count ‘a‘ (1 b a (c a)))  --> 1
• (countall ‘a‘ (1 b a (c a)))  -->  2

(reverse l) returns a list containing the elements of l in reverse order. You will probably want to use the append function.

• (reverse ‘(a b (c d) e))  -->  (e (c d) b a)

(twist l) reverses the top level of l and recursively twist all the items in l.

•  (twist ‘(a b (c d) e))  -->  (e (d c) b a)

(insertion-sort l) returns a sorted list of l using the Insertion Sort algorithm.

• (insertion-sort ‘(4 3 2 6 8 5))  -->  (2 3 4 5 6 8)

BONUS PROBLEM 1 : (permutations l) returns a list containing all the permutations of l.

• (permutations ‘(a b c))  -->  ((a b c) (a c b) (b a c) (b c a) (c a b) (c b a))

BONUS PROBLEM 2 : (powerset l) returns a list containing all the subsets of l which contains distinct elements.

• (powerset ‘(a b c))  -->  (() (a) (b) (c) (a b) (a c) (b c) (a b c))

 

---

ASaurcerfulofFunctions.py

from functools import reduce

# count x l
print(reduce(lambda acc, cur : acc + 1 if cur == 'a' else acc, [1, 'b', 'a', ['c', 'a']], 0))

# countall x l
def countall(lists):
  return reduce(lambda acc, cur : acc + countall(cur) if isinstance(cur, list) else acc + 1 if cur == 'a' else acc, lists, 0)
print(countall([1, 'b', 'a', ['c', 'a']]))

# reverse l
print(reduce(lambda acc, cur : [cur] + acc, ['a', 'b', ['c', 'd'], 'e'], []))

# twist l
def twist(lists):
  return reduce(lambda acc, cur : list(map(twist, [cur]) if isinstance(cur, list) else [cur]) + acc, lists, [])
print(twist(['a', 'b', ['c', 'd'], 'e']))

# insertion-sort l
print(reduce(lambda acc, cur : list(filter(lambda x : x < cur, acc)) + [cur] + list(filter(lambda x : x >= cur, acc)), [4, 3, 2, 6, 8, 5], []))

# BONUS : permutations l
def permutations(lists):
  return reduce(lambda acc, cur : acc + (list(map(lambda x : [cur] + list(x), permutations(list(filter(lambda y : y != cur, lists)))))) if list(filter(lambda y : y != cur, lists)) else [cur], lists, [])
print(permutations(['a', 'b', 'c']))

# BONUS : powerset l
def powerset(lists):
  return [[]] + reduce(lambda acc, cur : acc + (([[cur]] + list(map(lambda x : list(x) + [cur], acc)) if acc else [[cur]])), lists, [])
print(powerset(['a', 'b', 'c']))

 

함수형 프로그래밍 - 참고한 사이트:

파이썬 코딩 도장: 32.2 람다 표현식과 map, filter, reduce 함수 활용하기

 

Functional Thinking Chapter 2. 전환

 

강의노트 03. 파이썬 lambda, map, filter, reduce, dic · 초보몽키의 개발공부로그

 

함수형 프로그래밍 · JavaScript로 만나는 세상

 

함수형 프로그래밍 (재귀) - 참고한 사이트:

Reverse list using map/reduce

알고리즘 (순열(permutations)) - 참고한 사이트:

Generate all permutation of a set in Python - GeeksforGeeks

---

평가

"함수형 프로그래밍의 원칙을 지킨 좋은 코드입니다."