Haskell 初哥求教
时间:2014-04-08
来源:互联网
http://www.spoj.com/problems/INS14C/因我系初哥,所以个程式应该有好多地方可以改进。希望大家畀下意见:
main = do input <- getContents
doCase $ tail $ lines input
doCase :: [String] -> IO ()
doCase [] = return ()
doCase (nk : str : cases) = let [n, k] = map readInt $ words nk
in do doCase' n k str
doCase cases
doCase' :: Int -> Int -> String -> IO ()
doCase' n k = let sz = (n - k) `div` 2
so = (n - k + 1) `div` 2
in aux (sz, so, k)
aux :: (Int, Int, Int) -> String -> IO ()
aux (_, _, 0) _ = putStr "\n"
aux (0, so, k) ('0' : xs) = do putStr "0"
aux (0, so, k-1) xs
aux (sz, so, k) ('0' : xs) = aux (sz-1, so, k) xs
aux (sz, 0, k) ('1' : xs) = do putStr "1"
aux (sz, 0, k-1) xs
aux (sz, so, k) ('1' : xs) = aux (sz, so-1, k) xs
readInt :: String -> Int
readInt = read
作者: fitcat07 发布时间: 2014-04-08
用少点 IO... 尽量 purely functional
e.g. 另外分开 I/O 的方法,而不是将 putStr 放进主要算法的代码内
doCase 用了 tail recursion, 是否可以用 foldl / foldr 取代?
有关 signature 的问题,为何 aux 是 (Int, Int, Int) -> String -> [String]
而不是 Int -> Int -> Int -> String -> [String]
未有空去研究 XD
作者: stupidsing 发布时间: 2014-04-08
用少点 IO... 尽量 purely functional
e.g. 另外分开 I/O 的方法,而不是将 putStr 放进主要算法的代码内
我会再试下用 foldr 改写。
而不是 Int -> Int -> Int -> String -> [String]
我觉得学习 Haskell 对我并不容易,尤其用咗多年 imperative paradigm,要转做 functional paradigm,想法完全唔同。

就好似你指出嘅问题,虽则「知道」用 higher order functions 如 fold 会较好,但就唔明白「点解」。
今到程式较短及较易阅读?可能我系初哥,反而觉得较难理解。
我谂要写多尐,吸收经验,先会有唔同睇法。
希望改写后你能再给予我宝贵意见,感谢。

作者: fitcat07 发布时间: 2014-04-08
doCase 用了 tail recursion, 是否可以用 foldl / foldr 取代?
原本想用 foldr,但唔成功,我谂我未完全掌握得到。
我会再试下用 foldr 改写。
看过 prelude 又不见有适用的 function.
但不一定绝对要用 fold, 只系用左 high d 咁。
写 functional programming (fp) 成日系,用左乜乜乜又好似再 high d.
而不是 Int -> Int -> Int -> String -> [String]
原本构想系用 foldr,想令到三者变成一个 accumulator 之用。
不明白跟 foldr 的关连。
就好似你指出嘅问题,虽则「知道」用 higher order functions 如 fold 会较好,但就唔明白「点解」。
今到程式较短及较易阅读?可能我系初哥,反而觉得较难理解。
我谂要写多尐,吸收经验,先会有唔同睇法。
希望改写后你能再给予我宝贵意见,感谢。
例如没有了 mutable variable, 杜绝了一个变量多种用法的问题;
任何 iteration 都变成了 tail recursion,或其变种(fold 在 prelude 中的定义一样是 recursion)。
我觉得都是 Dont' repeat yourself 的理论,愈高层次的程式语言,可重用的程度愈高。
写 C 时不断出现for(int i=0;i<size;i++),
写 Java 时又不断有newlist=new arraylist(); for (elem

都是各种各样的重覆。
类似 fun [] = []; fun x:xs =... 的模式时常在fp 程式码出现,而最终可以将它变成一个 fold.
假如全team人都理解活用那些fp 用法,代码没有副作用,程式写得更快,bug 也较少,refactor也较易。
但实际上,系公司写 Java 写多两个 generic method已经畀人话唔知我做紧乜。
作者: stupidsing 发布时间: 2014-04-08
有个问题,因为那条 list 是两个项目为一组来读取的,正常的 fold 不能使用。
看过 prelude 又不见有适用的 function.
会唔会有 fold2 之类呢?
写 functional programming (fp) 成日系,用左乜乜乜又好似再 high d.

不明白跟 foldr 的关连。
foldr fun acc list
当中 acc 就系用 tuple 取代。唔知咁做好唔好?
例如没有了 mutable variable, 杜绝了一个变量多种用法的问题;
任何 iteration 都变成了 tail recursion,或其变种(fold 在 prelude 中的定义一样是 recursion)。
我睇过一个网站内嘅练习答案,都有唔少人留言话佢哋有唔同做法。
而话唔同嘅人写出嘅答案,感觉上真系好尐。
如果每个人都朝住「最佳」方法去写,我谂程式会好类同。
写 C 时不断出现for(int i=0;i<size;i++),
写 Java 时又不断有newlist=new arraylist(); for (elem

都是各种各样的重覆。
类似 fun [] = []; fun x:xs =... 的模式时常在fp 程式码出现,而最终可以将它变成一个 fold.
但实际上,系公司写 Java 写多两个 generic method已经畀人话唔知我做紧乜。

作者: fitcat07 发布时间: 2014-04-08
会唔会有 fold2 之类呢?
i.e. [a,b,c,d,e,f] becomes [[a,b],[c,d],[e,f]]
之后可以直接 fold.
[ 本帖最后由 stupidsing 於 2014-3-26 06:50 PM 编辑 ]
作者: stupidsing 发布时间: 2014-04-08
有了,用 iterate 配合 drop 2 的组合拳, 再 map take 2, 再 filter != [], 应该可以做到 one liner...
i.e. [a,b,c,d,e,f] becomes [[a,b],[c,d],[e,f]]
之后可以直接 fold.
我谂到咁做:
convert (x1:x2:xs) = (x1,x2) : convert xs

作者: fitcat07 发布时间: 2014-04-08
Prelude> drop 2 $ [1,2,3,4,5,6]
[3,4,5,6]
Prelude> take 9 . iterate (drop 2) $ [1,2,3,4,5,6]
[[1,2,3,4,5,6],[3,4,5,6],[5,6],[],[],[],[],[],[]]
Prelude> take 9 . map (take 2) . iterate (drop 2) $ [1,2,3,4,5,6]
[[1,2],[3,4],[5,6],[],[],[],[],[],[]]
Prelude> takeWhile (/= []) . map (take 2) . iterate (drop 2) $ [1,2,3,4,5,6]
[[1,2],[3,4],[5,6]]
其实都是对住 prelude 的 function 苦苦谂的。
作者: stupidsing 发布时间: 2014-04-08

睇完之后,刚刚上网搵到:
http://stackoverflow.com/questions/12876384/grouping-a-list-into-lists-of-n-elements-in-haskell
原来用 chunksOf 就做到。
另外,以下条 link 有人咁写:
http://stackoverflow.com/questions/5819649/splitting-list-into-n-tuples
不过,咁做会唔会影响 performance?
作者: fitcat07 发布时间: 2014-04-08
作者: form5 发布时间: 2014-04-08
车,自己米一样贴
1. 我谂呢度无乜人用 FP,无用过 FP 嘅人,应该睇咗都唔会明;
2. 就算有,我谂佢哋已经系高手,对第一题嚟讲,完全无难度,易如反掌;
3. 我目的唔系想话畀人知我识做,我张帖一早有讲;4. 我想搵人指正我写嘅 Haskell 码,唔贴唔得(我无喺原本张帖度贴);
5. 我想鼓励网友用唔同语言去做第一题,因此,我想做一个榜样。
唔知你满唔满意我嘅解释?
作者: fitcat07 发布时间: 2014-04-08
作者: form5 发布时间: 2014-04-08
理由冇一个认同,post code 除外

请问你点解要贴码?唔贴码就无意思?

你喜欢贴码,自己可以开新帖,随便贴。初阶至 Bubble sort,又或高阶好似汪汪贴 FFT。点解唔咁做?
作者: fitcat07 发布时间: 2014-04-08

作者: code4food 发布时间: 2014-04-08
而且更有一个好处,速度大幅增加,由 0.47s 减到 0.16s。
readInt :: String -> Int
readInt = read
main :: IO ()
main = do input <- getContents
let cases = takeWhile (not . null) $ unfoldr (Just . splitAt 2) $ tail $ lines input
mapM_ putStrLn $ map doCase' cases
doCase' :: [String] -> String
doCase' [nk, str] = let [n, k] = map readInt $ words nk
s0 = (n - k) `div` 2
s1 = (n - k + 1) `div` 2
in aux' (s0, s1, k) str
aux' :: (Int, Int, Int) -> String -> String
aux' (_, _, 0) _ = []
aux' (0, s1, k) ('0':inp) = '0' : aux' (0, s1, k-1) inp
aux' (s0, so, k) ('0':inp) = aux' (s0-1, so, k) inp
aux' (s0, 0, k) ('1':inp) = '1' : aux' (s0, 0, k-1) inp
aux' (s0, s1, k) ('1':inp) = aux' (s0, s1-1, k) inp
下一步,我想改进 aux' 呢个 function。初步谂用 guard 好似简单尐。另外,谂紧可唔可以用 higher order functions,将佢简化。
作者: fitcat07 发布时间: 2014-04-08
留名。Quarter end,忙到就嚟死得。


作者: fitcat07 发布时间: 2014-04-08
重有几日,等你出手。

作者: code4food 发布时间: 2014-04-08
你唔认同,我都无办法。

请问你点解要贴码?唔贴码就无意思?

你喜欢贴码,自己可以开新帖,随便贴。初阶至 Bubble sort,又或高阶好似汪汪贴 FFT。点解唔咁做?
作者: form5 发布时间: 2014-04-08
有时间的话当练习下姐,上黎睇完当做多次,我就吾理系边个嘅贴肋,我都几钟意有些题目
又或唔贴上最多人用嘅语言,如 C/C++/C#、Java、Pascal、Python、JavaScript、CoffeeScript 等。
只贴呢度少人用,但其实好正嘅语言,如 Ruby、Scala、Lua、Go、Dao、Clojure ...
又或唔用 imperative 或 OO paradigm,只用 functional programming 方式。
我呼吁唔好贴码,都系唔想其他人咁轻易见到答案,令佢哋失去兴趣咁啫。如果有心,都可能喺网上搵到答案。
作者: fitcat07 发布时间: 2014-04-08
readInt :: String -> Int
readInt = read
main :: IO ()
main = do input <- getContents
let cases = takeWhile (not . null) $ unfoldr (Just . splitAt 2) $ tail $ lines input
mapM_ (putStrLn . doCase) cases
doCase :: [String] -> String
doCase [nk, str] = let [n, k] = map readInt $ words nk
s0 = (n - k) `div` 2
s1 = (n - k + 1) `div` 2
(_, _, _, result) = foldl aux (s0, s1, k, []) str
in reverse result
where aux :: (Int, Int, Int, String) -> Char -> (Int, Int, Int, String)
aux (_, _, 0, result) _ = (0, 0, 0, result)
aux (0, s1, k, result) '0' = (0, s1, k-1, '0' : result)
aux (s0, s1, k, result) '0' = (s0-1, s1, k, result)
aux (s0, 0, k, result) '1' = (s0, 0, k-1, '1' : result)
aux (s0, s1, k, result) '1' = (s0, s1-1, k, result)
作者: fitcat07 发布时间: 2014-04-08
将 foldl 改成 foldr会快点吗?
作者: stupidsing 发布时间: 2014-04-08
作者: a8d7e8 发布时间: 2014-04-08
个人觉得 reverse 通常唔系咩好事,会牵涉 total copy.
将 foldl 改成 foldr会快点吗?
我都想知可唔可以有其他方法,避免用 reverse。

另外,我搵紧有冇可能当 k = 0 时,跳出 foldl,唔驶做晒每一个 str 嘅字元,但未搵到...
作者: fitcat07 发布时间: 2014-04-08

作者: fitcat07 发布时间: 2014-04-08
v3.hs:13:28: parse error on input `='
Line 13: s0 = (n - k) `div` 2
Glasgow Haskell Compiler, Version 7.6.3, stage 2 booted by GHC version 7.4.1
作者: a8d7e8 发布时间: 2014-04-08
Haskell 唔似其他 C/C++/Java 语言,唔系 free style,栏位系一定要对齐。
果行 s0 = ...,个 's' 字,一定要同上一行个 '[' 同一栏位。
我睇番我贴上去果段码,唔知点解由 let 下一行到 in 果 4 行,向右移咗一个栏位。
因此,你将个函数名加多一个字,就令到 '[' 向右移一位,亦令到佢哋对齐咗,而编译成功。
真系唔好意思。

作者: fitcat07 发布时间: 2014-04-08
foldl 改成 foldr, 去掉 reverse, flip 掉 aux, 不就成了吗?
没弄错的话 foldl 和 foldr 两者进行的次序是倒转的。
readInt :: String -> Int
readInt = read
main :: IO ()
main = do input <- getContents
let cases = takeWhile (not . null) $ unfoldr (Just . splitAt 2) $ tail $ lines input
mapM_ (putStrLn . doCase) cases
doCase :: [String] -> String
doCase [nk, str] = let [n, k] = map readInt $ words nk
s0 = (n - k) `div` 2
s1 = (n - k + 1) `div` 2
(_, _, _, result) = foldr aux (s0, s1, k, []) str
in result
where aux :: Char -> (Int, Int, Int, String) -> (Int, Int, Int, String)
aux _ (_, _, 0, result) = (0, 0, 0, result)
aux '0' (0, s1, k, result) = (0, s1, k-1, '0' : result)
aux '0' (s0, s1, k, result) = (s0-1, s1, k, result)
aux '1' (s0, 0, k, result) = (s0, 0, k-1, '1' : result)
aux '1' (s0, s1, k, result) = (s0, s1-1, k, result)
作者: stupidsing 发布时间: 2014-04-08
5 3
10010
作者: fitcat07 发布时间: 2014-04-08


我都觉 haskell 对 indentation 有要求...无想过那个位置要这样......
作者: a8d7e8 发布时间: 2014-04-08
问题系我嘅算法必须由左至右应用 aux。你嘅版本过唔到第一个测试范例:1
5 3
10010正确答案系 010,而你嘅答案系 100。

似乎下面二者皆可,但始终要空间进行倒序:
reverse . get4th . foldl aux (s0, s1, k, []) $ str
get4th . foldr (flip aux) (s0, s1, k, []) . reverse $ str
get4th (a, b, c, d) = d
作者: stupidsing 发布时间: 2014-04-08
readInt :: String -> Int
readInt = read
get4th :: (a, b, c, d) -> d
get4th (_, _, _, d) = d
main :: IO ()
main = do input <- getContents
let cases = takeWhile (not . null) $ unfoldr (Just . splitAt 2) $ tail $ lines input
putStr $ unlines $ map doCase cases
doCase :: [String] -> String
doCase [nk, str] = let [n, k] = map readInt $ words nk
s0 = (n - k) `div` 2
s1 = (n - k + 1) `div` 2
in reverse . get4th $ foldl aux (s0, s1, k, []) str
where aux :: (Int, Int, Int, String) -> Char -> (Int, Int, Int, String)
aux (_, _, 0, result) _ = (0, 0, 0, result)
aux (0, s1, k, result) '0' = (0, s1, k-1, '0' : result)
aux (s0, s1, k, result) '0' = (s0-1, s1, k, result)
aux (s0, 0, k, result) '1' = (s0, 0, k-1, '1' : result)
aux (s0, s1, k, result) '1' = (s0, s1-1, k, result)
作者: fitcat07 发布时间: 2014-04-08
热门阅读
-
office 2019专业增强版最新2021版激活秘钥/序列号/激活码推荐 附激活工具
阅读:74
-
如何安装mysql8.0
阅读:31
-
Word快速设置标题样式步骤详解
阅读:28
-
20+道必知必会的Vue面试题(附答案解析)
阅读:37
-
HTML如何制作表单
阅读:22
-
百词斩可以改天数吗?当然可以,4个步骤轻松修改天数!
阅读:31
-
ET文件格式和XLS格式文件之间如何转化?
阅读:24
-
react和vue的区别及优缺点是什么
阅读:121
-
支付宝人脸识别如何关闭?
阅读:21
-
腾讯微云怎么修改照片或视频备份路径?
阅读:28