Haskelを使用した基本データ構造の実装(1)-スタックとキュー1

アルゴリズムRepo
このアルゴリズム系列はHaskelを主とする.詳細な説明に比べて、学習中のハスク言語を学習するための位置づけであるため、漏れや間違いがある可能性があります.もし間違いがあったら、指摘してください.すぐ直しますから.
データ構造位置決めリスト

「配列」および「リスト」

スタック、キュー1(使用リスト)

ループインデックス

接続リスト1-単一接続リスト

スタック、キュー2(接続リストを使用)

接続リスト2-二重接続リスト、円形接続リスト

接続リスト3-利用接続リスト

バイナリツリー、マルチツリー

HIP(優先キュー)

グラフィック理論

利用図表

ハッシュテーブル

紹介する
この章では、スタックとキューの実装を試みます.接続リストは実装されていないため、リストとして実装する.
スタック
概要
スタックはデータ構造(FILO)であり、一端からのみデータを挿入して取り出すことができる.これは、後で挿入されるデータが最初に出力されることを意味します.たとえば、エディタでCtrl+Zを押して前の状態に戻すときにスタックを使用し、内部関数または再帰関数を読み込むときにスタックに関数データをスタックに積み上げます.内部関数の処理が完了したら、外部関数をスタックから取り出して実行します.
API

push(stack, element):スタック上部にデータを挿入

pop(stack):スタック上部のデータを取り出して出力します.

isEmpty(stack):スタックが空であることを確認

top(stack):スタック上部のデータが存在するかどうかを確認します.

コード#コード#
push

stackPush :: Num a => [a] -> a -> [a]
stackPush stack num = num:stack

スタックリストと追加する新しい値をパラメータとして受信し、変更されたスタックのステータス

を返します.

リストの先頭に追加する新しいデータを追加します.

テストコード

    let stack = []
    -- 1, 2, 3 순서로 puah
    
    -- element 1 push
    putStrLn "element 1 push"
    let stack1 = stackPush stack 1
    putStrLn ("stack status: " ++ show stack1)

    -- element 2 push
    putStrLn "element 2 push"
    let stack2 = stackPush stack1 2
    putStrLn ("stack status: " ++ show stack2)

    -- element 3 push
    putStrLn "element 3 push"
    let stack3 = stackPush stack2 3
    putStrLn ("stack status: " ++ show stack3)

結果

element 1 push
stack status: [1]
element 2 push
stack status: [2,1]
element 3 push
stack status: [3,2,1]

top

stackTop :: Num a => [a] -> Maybe a
stackTop [] = Nothing
stackTop stack = Just (head stack)

一番上(一番前)のデータを表示

stackTop []はスタックが空であることを示す.出力Nothingは空です.

stackTop stackは、上記スタックが空であることを除き、残りのスタックに少なくとも1つのデータが存在することを示す.head関数を使用して、最も前のデータのみを出力し、削除しません.

テストコード

let result = stackTop stack3
putStrLn ("top element: " ++ (show (fromJust result)))

... pop로 데이터를 전부 소거한 후 ...

-- empty by top
let result = stackTop stack0
putStrLn ("top element: " ++ (show result))

結果

top element: 3

... pop으로 데이터를 전부 소거한 후 ...
pop element: Nothing

Maybe? Just? Nothing?
先ほどのtop関数では、戻りタイプが少しおかしいことがわかります.stackTop :: Num a => [a] -> Maybe aデータを出力すると、前に突然Justが表示されます.stackTop stack = Just (head stack) Num aはaがNumであることを示す(整数、実数...)タイプであることを確認し、パラメータとして整数データを含むスタック[a]を受信し、整数タイプaに基づく変数を返します.そうしないと、前にMaybeが不思議に加算されます.Maybeはデータ型で、簡単に言えばNullをチェックします.これには、非Nullサブタイプを表すJustと、Nullが正しいNothingとが含まれる.したがって、パラメータ値または戻り値がNullである場合、前にMaybeを加算する.また、Maybe付きのデータ(Just)を使用するには、直接書き込むことはできません.前のfromJust関数を使用してMaybeタイプを削除する必要があります.

putStrLn ("top element: " ++ (show (fromJust result)))

NullじゃないとNullなのにどうしてこんなに複雑なプログラムなの?このような不満があるかもしれませんが、その理由はハスケルのI/Oタイプが非常に厳しいためです.C言語は任意のタイプのポインタ変数NULLを入力することができ、Javaは任意のタイプのnullを入力することができる.しかし、ハスケルの場合、タイプはタイプに一致するデータを含まなければならないため、既存のタイプにnullを追加することはできず、Maybetypeはnullであるかどうかを個別に決定することができる.面倒そうに見えますが、次のパブリッシュする接続リストでは、Maybeタイプがよく見られます.△筆者の推測ですが、Maybeを正しく理解するには、まずMonadを理解する必要があります.しかし、筆者はまだMonadを勉強しているので、後でこの内容を単独で紹介します.間違いがあれば、指摘してください.
pop

stackPop :: Num a => [a] -> ([a], Maybe a)
stackPop [] = ([], Nothing)
stackPop (element:stack) = (stack, Just element)

入力値としてスタックを受信し、戻りタイプをネスト(計算結果のスタック、先頭のデータ)とします.

stackTop []:スタックにデータは存在しません.スタック自体が空なので、もちろん何も実行できません.

stackTop (element:stack):スタックにデータが存在します.element:stack入力値スタックを前列データelementと前列データ以外のリストstackに分け、左側は前列データ以外の残りのリストstackを返し、右側は最近のデータelementを返す.

テストコード

    -- pop 3
    let result = stackPop stack3
    let stack2 = fst result
    let element = fromJust (snd result)
    putStrLn ("pop element: " ++ (show element))
    putStrLn ("stack status: " ++ (show stack2))

    -- pop 2
    let result = stackPop stack2
    let stack1 = fst result
    let element = fromJust (snd result)
    putStrLn ("pop element: " ++ (show element))
    putStrLn ("stack status: " ++ (show stack1))

    -- pop 1
    let result = stackPop stack1
    let stack0 = fst result
    let element = fromJust (snd result)
    putStrLn ("pop element: " ++ (show element))
    putStrLn ("stack status: " ++ (show stack0))

    -- empty
    let result = stackPop stack0
    let empty_stack = fst result
    let element = snd result
    putStrLn ("pop element: " ++ (show element))

fst, sndfstおよびsndはtupleが使用する関数であり、fstは左側の値を返し、sndは右側の値を返します.ただし、sndはtupleのデータ長が2の場合にのみ適用され、データ長が3より大きい場合にこの関数を使用するとエラーが発生します.
結果

pop element: 3
stack status: [2,1]
pop element: 2
stack status: [1]
pop element: 1
stack status: []
pop element: Nothing

isEmpty
スタックが空かどうかを確認します.

stackIsEmpty :: Num a => [a] -> Bool
stackIsEmpty [] = False
stackIsEmpty _ = True

キュー
概要
スタックとは異なり、これは「先入先出」(FIFO)のデータ構造です.すなわち,最初に入ったデータが最初に構造に入った.これは日常生活でよく使われる資料構造で、オペレーティングシステム(プロセススケジューリングなど)部分から、商店まで順番に接客して物品を計算します.
API

push(queue, element):データを挿入

pop(queue):ポップアップデータ

isEmpty(queue):キューが空であるかどうかを確認します.

コード#コード#
push

queuePush :: Num a => [a] -> a -> [a]
queuePush queue element = queue ++ [element]

スタックとは異なり、

はelementをキューの最後に追加します.データを追加したキューを返します.

テストコード

    let queue = []
    
    let queue2 = queuePush queue 1
    putStrLn ("Push 1: " ++ show queue2)

    let queue = queuePush queue2 2
    putStrLn ("Push 2: " ++ show queue)

    let queue2 = queuePush queue 3
    putStrLn ("Push 3: " ++ show queue2)

リターンマッチ

Push 1: [1]    
Push 2: [1,2]  
Push 3: [1,2,3]

pop

queuePop :: Num a => [a] -> ([a], Maybe a)
queuePop [] = ([], Nothing)
queuePop (element:queue) = (queue, Just element)

queuePop []:キューにデータがありません.

queuePop (element:queue)キューにデータが残っています.先頭のデータが先頭に入るデータであるため、先頭のデータとpop操作が終了したキューを返す.

テストコード

    -- pop 3
    let r = queuePop queue2
    let queue2 = fst r
    let e = fromMaybe 0 (snd r)
    putStrLn ("Pop: " ++ show e)
    
    -- pop 2
    let r = queuePop queue2
    let queue2 = fst r
    let e = fromMaybe 0 (snd r)
    putStrLn ("Pop: " ++ show e)

    -- pop 1
    let r = queuePop queue2
    let queue2 = fst r
    let e = fromMaybe 0 (snd r)
    putStrLn ("Pop: " ++ show e)

    
    -- empty error
    let r = queuePop queue2
    let queue2 = fst r
    let e = snd r
    putStrLn ("Pop: " ++ show e)

結果

Start pop      
Pop: 1
Pop: 2
Pop: 3
Pop: Nothing   

isEmpty

queueIsEmpty :: Num a => [a] -> Bool
queueIsEmpty queue = null queue

キューが空であるかどうかを確認するための関数です.nullは、Pythonのタイルが空であるかどうかを確認するために使用されるnotと同じであり、NULLではありません.null関数を使用して、リストが空であるかどうかを確認できます.