Haskell Kata 开坑

函数式编程 · asj · Created at · Last by asj Replied at · 1637 hits
377

缘起

前一段交流的发现。在TDD编写过程中,因为不熟悉函数式编程的思维方式,往往会先写成命令式的形式,再重构成函数式的样子。我回顾了一下发现,虽然在Java 8,Java Script,Scala中都接触了一点函数式,但是由于语言也支持命令式的写法,有了这个辅助轮就总是不能完全切换思维方式。
恰巧申导又抛了个函数式写因数分解的例子。就决定用一个纯函数式的语言试试。
本打算Clojure,结果Cyber-dojo不支持,干脆就选了Haskell。

进展

越写越觉得好玩,发现原来Scala中喜欢的特性,很多都有Haskell的影子。
目前已经练习了4次因数分解,2胜2败。后面考虑逐步尝试其它Kata
最满意的是把Unit Test从原来罗嗦的写法

test_1 = TestCase (assertEqual "message 1" (expect_1) (call1))
...
test_n = TestCase (assertEqual "message n" (expect_n) (call_n))
tests = TestList [test_1, test_2, ..., test_n]

改成了

tests = TestList $
  ("message 1" ~: expect_1 @=? call 1) :
  ...
  ("message n" ~: expect_n @=? call n) :
  []

发现网上还没有更好的例子,小得意一下。

资料和环境

教程看的是 Learn you a Haskell for great good! , 这里有中文版
在线环境除了Cyber-dojo外
还可以在 https://coderpad.io 里练习。不过这里没有测试框架可用。
Haskell官网或者 https://tryhaskell.org/ 上有个页面交互式的console, 不过行为也和 GHCi不完全一致。

代码

因数分解Kata
http://cyber-dojo.org/dashboard/show/2EF003C866
100 Doors
http://cyber-dojo.org/dashboard/show/F52B201234

最新一次代码如下

module Factors where

factorsOf (p:next_p) n
    | exact_div = p : factorsOf (p:next_p) next_n
    | no_more = []
    | n_is_prime = [n]
    | otherwise = factorsOf next_p n
    where
        next_n = n `div` p
        exact_div = n `mod` p == 0
        n_is_prime = n < p * p
        no_more = n == 1

factors :: Integer -> [Integer]
factors = factorsOf (2:[3,5..])
module TEST_Factors where

import Test.HUnit
import Factors

tests = TestList $ 
    ("1->[]" ~: [] @=? factors 1) :
    ("2->[2]" ~: [2] @=? factors 2) : 
    ("4->[2,2]" ~: [2,2] @=? factors 4) :
    ("3->[3]" ~: [3] @=? factors 3) :
    ("9->[3,3]" ~: [3,3] @=? factors 9) :
    ("100->[2,2,5,5]" ~: [2,2,5,5] @=? factors 100) :
    ("217->[7,31]" ~: [7,31] @=? factors 217) :
    ("510000002->[2,255000001]" ~: [2,255000001] @=? factors 510000002) :
    []
main = do runTestTT tests

召唤小伙伴

有兴趣的一起玩起来吧。Coderpad 在线结对也是蛮带感的。请回帖或者微信上找我 Vic-VVu


「软件匠艺社区」旨在传播匠艺精神,通过分享好的「工作方式」和「习惯」以帮助程序员更加快乐高效地编程。
共收到 1 条回复
377
asj · #1 ·

同一个dojo session下又做了两次。
使用fold

factors_to_list t@(n, ps) p 
    | n `mod` p == 0 = (next_n, new_ps)
    | otherwise = t
    where (next_n, new_ps) = factors_to_list (n `div` p, ps ++ [p]) p

factors :: Integer -> [Integer]
factors n = snd (foldl factors_to_list (n, []) [2..n])

缺点是数字较大时性能差,因为fold计算了整个小于n的数的列表。在这之前可能早已求出所有因子了。

改为scanl 加 filter,利用Haskell惰性求值终止fold过程,性能与递归方式相当。

no_more = ((==1) . fst)

check_factor pair@(n, ps) p 
    | no_more pair = pair
    | p_is_factor = (new_n, more_ps)
    | n_is_prime = (1, ps ++ [n])
    | otherwise = pair
    where 
        (new_n, more_ps) = check_factor (n `div` p, ps ++ [p]) p
        p_is_factor = n `mod` p == 0
        n_is_prime = p * p > n 

factors :: Integer -> [Integer]
factors n = 
    let return_once_get_all_factors = snd . head . filter no_more
    in  return_once_get_all_factors (scanl check_factor (n, []) [2..])
需要 Sign In 后回复方可回复, 如果你还没有账号你可以 Sign Up 一个帐号。