all2one awakening

얼마 전, Clojure & Python, Side by Side 글을 보고 나도 수도쿠(참고1) 살버를 해스켈로 포팅해보자 마음 먹었습니다. 먼저 원 고안자인 Peter Norvig의 글(참고2)을 읽고 찬찬히 읽고 알고리즘을 이해했습니다. 알고리즘을 특별히 함수형 언어에 적절하게 바꾸거나 하지 않고 그대로 포팅할 작정이었으므로, 기껏해야 네다섯 시간 투자하면 되겠거니 생각했습니다... 실제로는 투자한 시간을 합쳐보니 총 24시간은 넘을듯 하더군요;

• 일단, 여기 최종 해스켈 코드
  

코드보기

• 결과

원 파이썬 코드는 214행이었습니다. 제 해스켈 코드는 276행이군요. 원 노빅씨의 해법이 상당히 간결하다고 봤을 때, 나쁘지 않다고 봅니다.

성능은 다음처럼 나왔습니다. 보시다시피, 해스켈 버전이 약간 느리군요. 그래도 첫 시도로는 준수한 결과라 봅니다;

• 배운 것
• 수도쿠(참고1) 퍼즐 푸는 알고리즘, 노빅씨가 잘 설명해놓으셨습니다(참고2).
• 노빅씨의 파이썬 해법(참고2), 아름답습니다. (물론, 저는 파이썬 전문가 아닙니다;)
• 두 언어가 거의 동일하게 list comprehension(참고3)을 지원해서 편했습니다.
• C++에서와 같은 의미의 변수가 없다는 사실이 생각만큼 큰 차이로 느껴지지 않더군요.
• 후글(http://haskell.org/hoogle/)과 구글이 없었다면 24시간 정도만에 어림도 없었습니다.
• 기존 C 스타일의 언어에서 너무 익숙한 반복문과 반복문 내에서의 이른 탈출이 아예 없다는 것이 포팅에서의 가장 큰 걸림돌이었습니다.
• 함수형 언어에서는 반복이 아닌 재귀로 생각해야 합니다.
• 혹은 한단계 더 나아가 fold와 monad(참고5)로 생각해야 합니다.
• 해스켈에는 fold가 참 많습니다. foldl, foldr, foldl' 그리고 foldr'. 어떤 놈을 써야 할지 많이 헷갈리더군요(참고4).
• 이해하기 까다롭기로 소문난 모나드(참고5)가 자연스럽게 필요하게 되더군요. 이 놈 없으면 과도하게 중첩된 case 문을 사용하게 됩니다.
• 해스켈이 type inference를 지원하여 필수 사항은 아님에도, 형 선언을 꼬박꼬박 해주는게 이해하는데도 그렇고 디버깅 시에도 도움이 많이 되더군요.
• 책에서 읽은대로, 정말 해스켈로 짤 때에는, 컴파일이 되면 보통 바로 그대로 문제없이 동작하더군요. 물론, 컴파일이 되게 하기가 저한테는 쉽지 않았습니다만;
• IO 모나드에서 do 용법은 해스켈에서 일반 순수 함수를 짤 때와는 정말 다른 느낌이더군요. 흡사 다른 언어인 것처럼...;
• 해스켈의 특징인 laziness가 또 머리를 더 복잡하게 합니다. (제 코드에서 볼 수 있는 것처럼, 특정 상황에서는 결과를 얻기 위해 strict 계산을 강제해야 했습니다.)

• 결론
• 해스켈은 imperative programming language와는 완전 다른 세상이다...
• 해스켈 책 하나(제 경우는 "Real World Haskell"(참고9)) 읽은 것으로는, 해스켈로 적절히 코딩하기 힘들다. (파이썬 배울 때랑은 다르던군요.)
• 제 코드 분명 최선과는 거리가 멀겁니다. 노빅씨의 알고리즘을 그래도 포팅한다는 제약 조건 하에서도 분명 더 우아한 해법이 존재할겁니다. 그 제약 조건이 없으면, 물론 훨씬 다양한 해법이 존재하겠죠(참고10).
• 시간이 참 많이 걸렸지만, 그래도 유익한 코딩 연습이었다고 생각합니다. ^^

• 참고자료

1. Sudoku - Wikipedia: https://secure.wikimedia.org/wikipedia/en/wiki/Sudoku
2. Solving Every Sudoku Puzzle: http://norvig.com/sudoku.html
3. List comprehension - Wikipedia: https://secure.wikimedia.org/wikipedia/en/wiki/List_comprehension
4. Implications of foldr vs. foldl (or foldl'): http://stackoverflow.com/questions/384797/implications-of-foldr-vs-foldl-or-foldl
5. Monads for the Curious Programmer: http://bartoszmilewski.wordpress.com/2011/01/09/monads-for-the-curious-programmer-part-1/ http://bartoszmilewski.wordpress.com/2011/03/14/monads-for-the-curious-programmer-part-2/ http://bartoszmilewski.wordpress.com/2011/03/17/monads-for-the-curious-programmer-part-3/
6. Functional Programming For Beginners: http://ontwik.com/scala/functional-programming-for-beginners/
7. A Taste Of Haskell: http://ontwik.com/haskell/simon-peyton-jones-a-taste-of-haskell/
8. Learn You a Haskell for Great Good!: http://learnyouahaskell.com/
9. Real World Haskell: http://book.realworldhaskell.org/
10. Sudoku - HaskellWiki: http://www.haskell.org/haskellwiki/Sudoku
11. Haskell Cheat Sheet: http://blog.codeslower.com/static/CheatSheet.pdf

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.