Haskellでスタックを実装しよう！

スタックは、LIFO（Last In, First Out） 方式でデータを管理するデータ構造です。プログラミングにおいて、スタックは非常に基本的なデータ構造であり、再帰処理やブラウザの履歴、文字列操作などでよく使われます。この記事では、Haskellを使ってスタックをゼロから実装し、その使い方や応用例を紹介します。

1. スタックの基本操作

スタックには次の基本操作があります

1. push: 要素を追加する。

2. pop: 最後に追加した要素を取り出す。

3. isEmpty: スタックが空かどうかを確認する。

2. スタックの実装

Haskellで配列を使い、スタックを簡単に作ることができます。
Stack.hsというファイルにプログラムを書きましょう。

module Stack where

data Stack a = Stack [a] deriving Show

-- スタックを初期化
empty :: Stack a
empty = Stack []

-- 要素を追加
push :: a -> Stack a -> Stack a
push x (Stack xs) = Stack (x : xs)

-- 最後に追加した要素を取り出す
pop :: Stack a -> (a, Stack a)
pop (Stack (x:xs)) = (x, Stack xs)

-- スタックが空かどうかを確認
isEmpty :: Stack a -> Bool
isEmpty (Stack []) = True
isEmpty _         = False

3. スタックの使い方

スタックを使って、文字列を逆順にするプログラムを書いてみましょう。
Main.hsというファイルにプログラムを保存します。

import Stack

reverseString :: String -> String
reverseString str = reverseHelper (foldl (flip push) empty str)

reverseHelper :: Stack Char -> String
reverseHelper stack
    | isEmpty stack = ""
    | otherwise = let (x, newStack) = pop stack
                  in x : reverseHelper newStack

main :: IO ()
main = do
    let result = reverseString "Haskell"
    putStrLn result

4. 実行する

Haskellの環境構築は、こちらを確認してください。

下記のコマンドで、プログラムを実行します

runhaskell Main.hs

lleksaH と表示されれば成功です！

まとめ

スタックはシンプルですが、文字列操作や括弧チェックなど多くの場面で使われます。Haskellを使えば、簡単に実装して応用できます。ぜひ試してみてください！