線形探索、累積和、二分探索、Two Pointer を Haskell で書いたメモです。 命令型ならインデックスで進める処理を、再帰とリストでどう置いたかを残しています。

線形探索

再帰で先頭から順に探します。== で比べるので、型は Eq a です。

linearSearch :: (Eq a) => a -> [a] -> Bool
linearSearch _ [] = False
linearSearch target (x : xs)
    | target == x = True
    | otherwise = linearSearch target xs

main :: IO ()
main = print $ linearSearch 3 [2, 4, 3]

実行結果

True

空なら False、先頭が一致なら True、それ以外は残りを同じ関数に渡します。 こういった単純にリストの前から順に探していくアルゴリズムでも、再帰的に書くのが Haskell っぽいなと感じます。

累積和

各位置までの和を、その位置の値として並べます。[2, 3, 4] なら [2, 5, 9] です。先頭に 0 を置いた列は返しません。

prefixSum :: (Num x) => [x] -> [x]
prefixSum = scanl1 (+)

main :: IO ()
main = print $ prefixSum [2, 3, 4]

実行結果

[2, 5, 9]

Haskell には scanl1 という関数があり、左から順に関数を適用して結果をリストに残します。これを使うと累積和を短く書けます。

二分探索

条件がどこかで False から True に切り替わるとき、最初に True になる整数を返します。最初の引数が条件、次がまだ満たさない側、最後が満たす側です。

binarySearch :: (Int -> Bool) -> Int -> Int -> Int
binarySearch predicate = go
  where
    go ng ok
        | ok - ng <= 1 = ok
        | predicate mid = go ng mid
        | otherwise = go mid ok
      where
        mid = ng + (ok - ng) `div` 2

main :: IO ()
main = print $ binarySearch (\x -> x * x >= 10) 0 10

実行結果

4

例では 0 から 10 の範囲で、最初に x * x >= 10 となる x を探しています。3 * 3 = 9 は条件を満たさず、4 * 4 = 16 は満たすので、結果は 4 になります。 Haskell だと問題ごとの条件は predicate に切り出せるので、探索の骨格と「何を探すか」が分離されて読みやすいです。

Two Pointer

ソート済みリストから、和が target になる 2 要素があるかを両端から探します。ソートしていないリストに使うと、組があっても False になります。

twoPointer :: (Ord a, Num a) => a -> [a] -> Bool
twoPointer target xs = go (length xs) xs (reverse xs)
  where
    go remaining (l : ls) (r : rs)
        | remaining <= 1 = False
        | otherwise =
            case compare (l + r) target of
                EQ -> True
                LT -> go (remaining - 1) ls (r : rs)
                GT -> go (remaining - 1) (l : ls) rs
    go _ _ _ = False

main :: IO ()
main = print $ twoPointer 9 [1, 3, 4, 5, 7, 10]

実行結果

True

例では [1, 3, 4, 5, 7, 10] から和が 9 になる組を探していて、4 + 5 = 9 が見つかるので True です。 和が小さければ左を進め、大きければ右を戻します。インデックスの代わりに元のリストと reverse したリストを並べて再帰しているのが Haskell らしいです。

まとめ

Coding Agent が出てきてから自分の手でコードを書く機会がめっきり減りました。しかし、Haskellのような普段書いている言語とは違うパラダイムの言語でコードを書くと、思考モデルそのもの変える力があると感じます。AI時代でコードを書く能力そのものはもしかしたら価値が減っていくかもしれませんが、使うことで思考モデルが変わる言語を書くことはこれからも意味があるかもしれません。