Haskell 99 Questions :: 0x01
archive time: 2024-10-30
闲来无事,来练习一下 Haskell
缘起
我最近不知为何突然喜欢上了 Tsoding 的视频, 其中 有一期视频 提到了 99 questions, 那么我也就顺便来做一下吧
准备
我打算使用 Haskell 来解决这些问题, 实际上,基本所有的支持函数式编程的语言(包括 C 语言)都能解决这些问题, 只是有些语言实现起来方便一些罢了
但是如果仔细看里面的问题的话就会发现,其中还有随机数这种问题, 虽然我们可以通过某些算法来生成一些不那么随机的伪随机数, 但是更加方便的方案还是调用 random 库, 不过这就要求我们需要创建一个 Haskell 项目才行
不过我们还有一种方法,那就是读取 /dev/random
文件,具体实现如下:
module Qarks.Random (readRandomBytes) where
import Data.Word (Word8)
import Foreign.Marshal.Alloc (mallocBytes)
import Foreign.Ptr (plusPtr)
import Foreign.Storable (peek)
import System.IO (IOMode (..), hClose, hGetBuf, openFile)
readRandomBytes :: Int -> IO [Word8]
readRandomBytes n = do
handle <- openFile "/dev/random" ReadMode
buf <- mallocBytes n
_ <- hGetBuf handle buf n
bytes <- mapM (peek . plusPtr buf) [0 .. (n - 1)]
hClose handle
return bytes
使用 Foreign
是为了避免读取到非法字符编码出错,所以读取字节,
最后返回的是一个 Word8
列表,可以通过其他方法把这些数字变成具体的想要随即的内容,例如浮点数或字符
题目
Question 01
Find the last element of a list.
返回列表中的最后一个元素,空列表返回 Nothing
qLastOne :: [a] -> Maybe a
答案
qLastOne :: [a] -> Maybe a
qLastOne [] = Nothing
qLastOne [e] = Just e
qLastOne (_ : t) = qLastOne t
Question 02
Find the last-but-one (or second-last) element of a list.
返回列表中的倒数第二个元素,
列表元素长度小于 2
返回 Nothing
qLastTwo :: [a] -> Maybe a
答案
qLastTwo :: [a] -> Maybe a
qLastTwo [] = Nothing
qLastTwo [_] = Nothing
qLastTwo [e, _] = Just e
qLastTwo (_ : t) = qLastTwo t
Question 03
Find the K-th element of a list.
返回第 K
位元素,
列表长度小于 K
返回 Nothing
,K
从 1
开始
qKthElement :: [a] -> Int -> Maybe a
答案
qKthElement :: [a] -> Int -> Maybe a
qKthElement (e : _) 1 = Just e
qKthElement [] _ = Nothing
qKthElement (_ : t) k
| k < 1 = Nothing
| otherwise = qKthElement t (k - 1)
Question 04
Find the number of elements in a list.
返回列表长度,这个比较直接
qLength :: [a] -> Int
答案
qLength :: [a] -> Int
qLength lst = qLengthI lst 0
where
qLengthI :: [a] -> Int -> Int
qLengthI [] n = n
qLengthI (_ : t) n = qLengthI t (n + 1)
Question 05
Reverse a list.
翻转列表
qReverse :: [a] -> [a]
答案
qReverse :: [a] -> [a]
qReverse [] = []
qReverse lst = qReverseI lst []
where
qReverseI :: [a] -> [a] -> [a]
qReverseI [] acc = acc
qReverseI (h : t) acc = qReverseI t (h : acc)
Question 06
Find out whether a list is a palindrome.
判断列表是否是回文列表
qIsPalindrome :: (Eq a) => [a] -> Bool
答案
qIsPalindrome :: (Eq a) => [a] -> Bool
qIsPalindrome lst = lst == qReverse lst
Question 07
Flatten a nested list structure.
将一个嵌套结构的列表摊平,也就是变成一维结构
data QNestedList a = QElem a | QList [QNestedList a]
deriving (Show, Eq)
qFlatten :: QNestedList a -> [a]
答案
data QNestedList a = QElem a | QList [QNestedList a]
deriving (Show, Eq)
qFlatten :: QNestedList a -> [a]
qFlatten (QElem e) = [e]
qFlatten (QList nlst) = qReverse (qFlattenI nlst [])
where
qFlattenI :: [QNestedList a] -> [a] -> [a]
qFlattenI [] acc = acc
qFlattenI (QElem e : t) acc = qFlattenI t (e : acc)
qFlattenI (QList qlst : t) acc = qFlattenI t (qFlattenI qlst [] ++ acc)
Question 08
Eliminate consecutive duplicates of list elements.
将连续的重复元素合并成一个
qCompress :: (Eq a) => [a] -> [a]
答案
qCompress :: (Eq a) => [a] -> [a]
qCompress lst = qCompressI lst []
where
qCompressI :: (Eq a) => [a] -> [a] -> [a]
qCompressI [] acc = acc
qCompressI [e] acc = e : acc
qCompressI (x : y : t) acc =
qCompressI
(y : t)
(if x == y then acc else x : acc)
Question 09
Pack consecutive duplicates of list elements into sublists.
将重复元素合并成一个子列表
qPack :: (Eq a) => [a] -> [[a]]
答案
qPack :: (Eq a) => [a] -> [[a]]
qPack lst = qReverse (qPackI lst [] [])
where
qPackI :: (Eq a) => [a] -> [a] -> [[a]] -> [[a]]
qPackI [] p acc = p : acc
qPackI (h : t) [] acc = qPackI t [h] acc
qPackI (h : t) (x : xs) acc
| h == x = qPackI t (h : x : xs) acc
| otherwise = qPackI t [h] ((x : xs) : acc)
Question 10
Run-length encoding of a list.
利用 Question 09 的结果来实现 Run-length 编码
qRunLengthEncode :: (Eq a) => [a] -> [(Int, a)]
答案
qRunLengthEncode :: (Eq a) => [a] -> [(Int, a)]
qRunLengthEncode lst = map (\p -> (qLength p, head p)) (qPack lst)
测试用例
我这里使用了 hspec 测试框架来测试结果,具体的测试代码如下:
测试代码
module Part01 (part01) where
import Qarks.Nnp
( QNestedList (..),
qCompress,
qFlatten,
qIsPalindrome,
qKthElement,
qLastOne,
qLastTwo,
qLength,
qPack,
qReverse,
qRunLengthEncode,
)
import Test.Hspec (context, describe, it, shouldBe, shouldNotSatisfy, shouldSatisfy)
import Test.Hspec.Runner (SpecWith)
part01 :: SpecWith ()
part01 = describe "Part01" $
do
context "Qarks.Nnp.qLastOne" $ do
it "[1 .. 4]" $ do
qLastOne [1 .. 4] `shouldBe` Just (4 :: Int)
it "['a' .. 'z']" $ do
qLastOne ['a' .. 'z'] `shouldBe` Just 'z'
context "Qarks.Nnp.qLastTwo" $ do
it "[1 .. 4]" $ do
qLastTwo [1 .. 4] `shouldBe` Just (3 :: Int)
it "['a' .. 'z']" $ do
qLastTwo ['a' .. 'z'] `shouldBe` Just 'y'
context "Qarks.Nnp.qKthElement" $ do
it "2-nd of [1, 2, 3]" $ do
qKthElement [1, 2, 3] 2 `shouldBe` Just (2 :: Int)
it "5-th of \"haskell\"" $ do
qKthElement "haskell" 5 `shouldBe` Just 'e'
context "Qarks.Nnp.qLength" $ do
it "[123, 456, 789]" $ do
qLength [123 :: Int, 456, 789] `shouldBe` 3
it "\"Hello, world!\"" $ do
qLength "Hello, world!" `shouldBe` 13
context "Qarks.Nnp.qReverse" $ do
it "\"A man, a plan, a canal, panama!\"" $ do
qReverse "A man, a plan, a canal, panama!"
`shouldBe` "!amanap ,lanac a ,nalp a ,nam A"
it "[1 .. 4]" $ do
qReverse [1 .. 4] `shouldBe` [4 :: Int, 3, 2, 1]
context "Qarks.Nnp.qIsPalindrome" $ do
it "[1, 2, 3]" $ do
[1 :: Int, 2, 3] `shouldNotSatisfy` qIsPalindrome
it "\"madamimadam\"" $ do
"madamimadam" `shouldSatisfy` qIsPalindrome
it "[1, 2, 4, 8, 16, 8, 4, 2, 1]" $ do
[1 :: Int, 2, 4, 8, 16, 8, 4, 2, 1] `shouldSatisfy` qIsPalindrome
context "Qarks.Nnp.qFlatten" $ do
it "QElem 5" $ do
qFlatten (QElem 5) `shouldBe` [5 :: Int]
it "QList [QElem 1, QList [QElem 2, QList [QElem 3, QElem 4], QElem 5]]" $ do
qFlatten (QList [QElem 1, QList [QElem 2, QList [QElem 3, QElem 4], QElem 5]])
`shouldBe` [1 :: Int .. 5]
it "QList []" $ do
qFlatten (QList []) `shouldBe` ([] :: [Int])
context "Qarks.Nnp.qCompress" $ do
it "\"aaaabccaadeeee\"" $ do
qCompress "aaaabccaadeeee" `shouldBe` "abcade"
context "Qarks.Nnp.qPack" $ do
it "\"aaaabccaadeeee\"" $ do
qPack "aaaabccaadeeee"
`shouldBe` ["aaaa", "b", "cc", "aa", "d", "eeee"]
context "Qarks.Nnp.qRunLengthEncode" $ do
it "\"aaaabccaadeeee\"" $ do
qRunLengthEncode "aaaabccaadeeee"
`shouldBe` [(4, 'a'), (1, 'b'), (2, 'c'), (2, 'a'), (1, 'd'), (4, 'e')]
测试主函数如下:
module Main (main) where
import Part01 (part01)
import Test.Hspec (hspec)
main :: IO ()
main = hspec $ do
part01
之后的测试代码我就不再重复主函数部分了