+ -
当前位置:首页 → 问答吧 → Haskell 初哥求教

Haskell 初哥求教

时间:2014-04-08

来源:互联网

我用 Haskell 完成咗以下编程问题:
http://www.spoj.com/problems/INS14C/因我系初哥,所以个程式应该有好多地方可以改进。希望大家畀下意见:
复制内容到剪贴板代码:main :: IO ()
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

引用:原帖由 stupidsing 於 2014-3-26 02:29 PM 发表
用少点 IO... 尽量 purely functional
e.g. 另外分开 I/O 的方法,而不是将 putStr 放进主要算法的代码内
我初初系想咁做,但唔成功,於是做成宜家咁...我有谂过建立一条 String 作为最后输出之用,会再试试。
引用:doCase 用了 tail recursion, 是否可以用 foldl / foldr 取代?
原本想用 foldr,但唔成功,我谂我未完全掌握得到。
我会再试下用 foldr 改写。
引用:有关 signature 的问题,为何 aux 是 (Int, Int, Int) -> String -> [String]
而不是 Int -> Int -> Int -> String -> [String]
原本构想系用 foldr,想令到三者变成一个 accumulator 之用。

我觉得学习 Haskell 对我并不容易,尤其用咗多年 imperative paradigm,要转做 functional paradigm,想法完全唔同。另一样嘢感到困扰系,好多时有多种方法可以做到,我唔识得分好坏。
就好似你指出嘅问题,虽则「知道」用 higher order functions 如 fold 会较好,但就唔明白「点解」。
今到程式较短及较易阅读?可能我系初哥,反而觉得较难理解。
我谂要写多尐,吸收经验,先会有唔同睇法。

希望改写后你能再给予我宝贵意见,感谢。

作者: fitcat07   发布时间: 2014-04-08

引用:我初初系想咁做,但唔成功,於是做成宜家咁...我有谂过建立一条 String 作为最后输出之用,会再试试。

doCase 用了 tail recursion, 是否可以用 foldl / foldr 取代?

原本想用 foldr,但唔成功,我谂我未完全掌握得到。
我会再试下用 foldr 改写。
有个问题,因为那条 list 是两个项目为一组来读取的,正常的 fold 不能使用。
看过 prelude 又不见有适用的 function.

但不一定绝对要用 fold, 只系用左 high d 咁。
写 functional programming (fp) 成日系,用左乜乜乜又好似再 high d.
引用: 有关 signature 的问题,为何 aux 是 (Int, Int, Int) -> String -> [String]
而不是 Int -> Int -> Int -> String -> [String]

原本构想系用 foldr,想令到三者变成一个 accumulator 之用。
通常 a -> b -> c 可以容许 currying.
不明白跟 foldr 的关连。
引用:我觉得学习 Haskell 对我并不容易,尤其用咗多年 imperative paradigm,要转做 functional paradigm,想法完全唔同。另一样嘢感到困扰系,好多时有多种方法可以做到,我唔识得分好坏。
就好似你指出嘅问题,虽则「知道」用 higher order functions 如 fold 会较好,但就唔明白「点解」。
今到程式较短及较易阅读?可能我系初哥,反而觉得较难理解。
我谂要写多尐,吸收经验,先会有唔同睇法。

希望改写后你能再给予我宝贵意见,感谢。
我反而觉得,fp 限制了程式员去用单一的方法,所以同一个算法(由不同人)写出来的代码会较相似。
例如没有了 mutable variable, 杜绝了一个变量多种用法的问题;
任何 iteration 都变成了 tail recursion,或其变种(fold 在 prelude 中的定义一样是 recursion)。

我觉得都是 Dont' repeat yourself 的理论,愈高层次的程式语言,可重用的程度愈高。
写 C 时不断出现for(int i=0;i<size;i++),
写 Java 时又不断有newlist=new arraylist(); for (elemldlist) newlist.add(elem.abc());,
都是各种各样的重覆。
类似 fun [] = []; fun x:xs =... 的模式时常在fp 程式码出现,而最终可以将它变成一个 fold.

假如全team人都理解活用那些fp 用法,代码没有副作用,程式写得更快,bug 也较少,refactor也较易。
但实际上,系公司写 Java 写多两个 generic method已经畀人话唔知我做紧乜。

作者: stupidsing   发布时间: 2014-04-08

引用:原帖由 stupidsing 於 2014-3-26 05:09 PM 发表
有个问题,因为那条 list 是两个项目为一组来读取的,正常的 fold 不能使用。
看过 prelude 又不见有适用的 function.
要同时间处理两个 list members,好似无方法做,起码我唔识...
会唔会有 fold2 之类呢?
引用:但不一定绝对要用 fold, 只系用左 high d 咁。
写 functional programming (fp) 成日系,用左乜乜乜又好似再 high d.
哈哈,我学 Haskell 其中一个原因,就系写到之后,有尐 high high 地嘅感觉,有尐变态...
引用:通常 a -> b -> c 可以容许 currying.
不明白跟 foldr 的关连。
其实我想将 3 个数据 sz, so 同 k,变成一个 tuple,咁就好似符合 fold 定义:
foldr fun acc list
当中 acc 就系用 tuple 取代。唔知咁做好唔好?
引用:我反而觉得,fp 限制了程式员去用单一的方法,所以同一个算法(由不同人)写出来的代码会较相似。
例如没有了 mutable variable, 杜绝了一个变量多种用法的问题;
任何 iteration 都变成了 tail recursion,或其变种(fold 在 prelude 中的定义一样是 recursion)。
呢点我赞同。
我睇过一个网站内嘅练习答案,都有唔少人留言话佢哋有唔同做法。
而话唔同嘅人写出嘅答案,感觉上真系好尐。
如果每个人都朝住「最佳」方法去写,我谂程式会好类同。
引用:我觉得都是 Dont' repeat yourself 的理论,愈高层次的程式语言,可重用的程度愈高。
写 C 时不断出现for(int i=0;i<size;i++),
写 Java 时又不断有newlist=new arraylist(); for (elemldlist) newlist.add(elem.abc());,
都是各种各样的重覆。
类似 fun [] = []; fun x:xs =... 的模式时常在fp 程式码出现,而最终可以将它变成一个 fold.
因此,C++/Java 都加入 FP 嘅处事方式。似乎 FP 系大势所趋。
引用:假如全team人都理解活用那些fp 用法,代码没有副作用,程式写得更快,bug 也较少,refactor也较易。
但实际上,系公司写 Java 写多两个 generic method已经畀人话唔知我做紧乜。
喺香港,交到货系最重要。只要件货「外表」无问题,即使里面用浆糊、胶纸,甚至「吊吊 fing」,我谂都无人理,只要个客睇唔到就得。

作者: fitcat07   发布时间: 2014-04-08

引用:要同时间处理两个 list members,好似无方法做,起码我唔识...
会唔会有 fold2 之类呢?
有了,用 iterate 配合 drop 2 的组合拳, 再 map take 2, 再 take while != [], 应该可以做到 one liner...

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

引用:原帖由 stupidsing 於 2014-3-26 06:23 PM 发表
有了,用 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.
WOW,好复杂喎...
我谂到咁做:
复制内容到剪贴板代码:convert [] = []
convert (x1:x2:xs) = (x1,x2) : convert xs
但又系 recursion 版。

作者: 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
复制内容到剪贴板代码:takeWhile (not.null) $ unfoldr (Just . splitAt n)
原本系 . 唔 work,改咗做 $ 就 OK。
不过,咁做会唔会影响 performance?

作者: fitcat07   发布时间: 2014-04-08

车,自己米一样贴

作者: form5   发布时间: 2014-04-08

引用:原帖由 form5 於 2014-3-26 09:23 PM 发表
车,自己米一样贴
以下系我嘅理由:
1. 我谂呢度无乜人用 FP,无用过 FP 嘅人,应该睇咗都唔会明;
2. 就算有,我谂佢哋已经系高手,对第一题嚟讲,完全无难度,易如反掌;
3. 我目的唔系想话畀人知我识做,我张帖一早有讲;4. 我想搵人指正我写嘅 Haskell 码,唔贴唔得(我无喺原本张帖度贴);
5. 我想鼓励网友用唔同语言去做第一题,因此,我想做一个榜样。

唔知你满唔满意我嘅解释?

作者: fitcat07   发布时间: 2014-04-08

理由冇一个认同,post code 除外

作者: form5   发布时间: 2014-04-08

引用:原帖由 form5 於 2014-3-27 12:29 AM 发表
理由冇一个认同,post code 除外
你唔认同,我都无办法。

请问你点解要贴码?唔贴码就无意思?
你喜欢贴码,自己可以开新帖,随便贴。初阶至 Bubble sort,又或高阶好似汪汪贴 FFT。点解唔咁做?

作者: fitcat07   发布时间: 2014-04-08

留名。Quarter end,忙到就嚟死得。

作者: code4food   发布时间: 2014-04-08

听取意见后,将 IO 同主算法分开,程式码系远较之前清楚。
而且更有一个好处,速度大幅增加,由 0.47s 减到 0.16s。
复制内容到剪贴板代码:import Data.List

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
我原本想比较 chunksOf、studpidsing 写法同网上搵到嘅写法(splitAt)三者效能,可惜 SPOJ 嘅 GHC compiler 太旧(6.10.4),唔支援 Data.List.Split(chunksOf 需要)。而后两者写法喺效能上无分别。

下一步,我想改进 aux' 呢个 function。初步谂用 guard 好似简单尐。另外,谂紧可唔可以用 higher order functions,将佢简化。

作者: fitcat07   发布时间: 2014-04-08

引用:原帖由 code4food 於 2014-3-27 12:07 PM 发表
留名。Quarter end,忙到就嚟死得。
重有几日,等你出手。

作者: fitcat07   发布时间: 2014-04-08

引用:原帖由 fitcat07 於 2014-3-26 11:24 PM 发表
重有几日,等你出手。
公司忙完到屋企野忙。真系就嚟死啦。

作者: code4food   发布时间: 2014-04-08

引用:原帖由 fitcat07 於 2014-3-27 11:57 AM 发表
你唔认同,我都无办法。

请问你点解要贴码?唔贴码就无意思?
你喜欢贴码,自己可以开新帖,随便贴。初阶至 Bubble sort,又或高阶好似汪汪贴 FFT。点解唔咁做?
有时间的话当练习下姐,上黎睇完当做多次,我就吾理系边个嘅贴肋,我都几钟意有些题目

作者: form5   发布时间: 2014-04-08

引用:原帖由 form5 於 2014-3-27 08:56 PM 发表

有时间的话当练习下姐,上黎睇完当做多次,我就吾理系边个嘅贴肋,我都几钟意有些题目
不如你自己开一个帖,如叫「我的程式码」或「我的解答」之类,将答案贴上去,再喺我张帖留言,加条 link 指过去,咁好唔好?
又或唔贴上最多人用嘅语言,如 C/C++/C#、Java、Pascal、Python、JavaScript、CoffeeScript 等。
只贴呢度少人用,但其实好正嘅语言,如 Ruby、Scala、Lua、Go、Dao、Clojure ...
又或唔用 imperative 或 OO paradigm,只用 functional programming 方式。

我呼吁唔好贴码,都系唔想其他人咁轻易见到答案,令佢哋失去兴趣咁啫。如果有心,都可能喺网上搵到答案。

作者: fitcat07   发布时间: 2014-04-08

试过用 guard,冇简化到。改咗 doCase 用 foldl:
复制内容到剪贴板代码:import Data.List

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)
效能无影响,仍然系 0.16s。

作者: fitcat07   发布时间: 2014-04-08

个人觉得 reverse 通常唔系咩好事,会牵涉 total copy.
将 foldl 改成 foldr会快点吗?

作者: stupidsing   发布时间: 2014-04-08

唔知点解全部 doCase 要改做 doCase' 先 compile 到.

作者: a8d7e8   发布时间: 2014-04-08

引用:原帖由 stupidsing 於 2014-3-28 11:38 AM 发表
个人觉得 reverse 通常唔系咩好事,会牵涉 total copy.
将 foldl 改成 foldr会快点吗?
唔知系咪我唔明,初初曾经试过用 foldr,但做唔到,原因除咗 aux 唔系 associative 之外,我嘅算法必须由左至右 apply aux。
我都想知可唔可以有其他方法,避免用 reverse。
另外,我搵紧有冇可能当 k = 0 时,跳出 foldl,唔驶做晒每一个 str 嘅字元,但未搵到...

作者: fitcat07   发布时间: 2014-04-08

咁奇怪?

作者: fitcat07   发布时间: 2014-04-08

[1 of 1] Compiling Main ( v3.hs, v3.o )

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 两者进行的次序是倒转的。
引用:import Data.List

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

问题系我嘅算法必须由左至右应用 aux。你嘅版本过唔到第一个测试范例:
复制内容到剪贴板代码:1
5 3
10010
正确答案系 010,而你嘅答案系 100。

作者: fitcat07   发布时间: 2014-04-08

哇!! 应验了 correlation is not causation.

我都觉 haskell 对 indentation 有要求...无想过那个位置要这样......

作者: a8d7e8   发布时间: 2014-04-08

引用:原帖由 fitcat07 於 2014-3-29 12:23 PM 发表
问题系我嘅算法必须由左至右应用 aux。你嘅版本过唔到第一个测试范例:1
5 3
10010正确答案系 010,而你嘅答案系 100。
原来睇错code...... 陷入假设症状。
似乎下面二者皆可,但始终要空间进行倒序:
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

加入你嘅改变及将 mapM_ (putStrLn . doCase) 改为 putStr $ unlines $ map doCase, 最新版本:
复制内容到剪贴板代码:import Data.List

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

热门下载

更多