Haskell 多重リスト - あしひきの

この言葉が廣く使はれてゐるのかは知らない
多次元リストといふ言葉もネットに載ってゐる
リストの中にリストがあるといった意味合ひで使はれるのだらうとは思ふ
例へば
[[1,2],[1,2,3],[4],[6,5,4,3]]
といったものだらう
だが私としては「多重リスト」といふ言葉を
「リストの中に「リストのリスト」も「リストのリストのリスト」も含むやうなリスト」
の意味で使ひたい
いや既にそれを表す用語があるのならそれを使ふのだが今私はそれを知らないから

つまり多重リストといふのは私にとって
[1, [2,3], [3,[4,5]], [[[6,7],[8]]]]
のやうに書けるやうなものだ
多分 Haskell ではかういうのはリストと言はないだらうが

これはおそらく構造としては「木」の構造だから「木」と呼ぶべきなのだらう
けれども上の表記はそれなりにデータの構造が分かりやすく可視化できてゐると思ふ
Data.Tree モジュールを利用してこの構造を實装し可視化しやうとしたのが私のつくった MyTreeモジュールだ

github.com

module MyTree (Elm(..), showF, addElem) where

import Data.Tree 
import Data.List (intercalate)

data Elm a = El a Int Int

showT :: Show a => Tree a -> String 
showT (Node x []) = show x
showT (Node x tr) = "["++show x++", "++tail (showF tr)

showF :: Show a => Forest a -> String 
showF [] = ""
showF tr = "[" ++ intercalate ", " (map showT tr) ++ "]"

addElem :: Elm a -> Forest a -> Forest a 
addElem (El mn _ _) [] = [Node mn []]
addElem (El mn 0 0) fo = fo ++ [Node mn []]
addElem (El mn l r) fo
  | lng > l && l > 0 = let (h,(Node s sf):t) = splitAt (lng - l) fo
                           newNode = Node s (t++addElem (El mn l r) sf)
                        in h ++ [newNode]
  | r > 0 = let (it,lt) = (init fo,last fo)
                Node x subf = lt  -- last tree
             in if null subf then it ++ [lt, Node mn []]
                             else it ++ [Node x (addElem (El mn l r) subf)]
  | otherwise = fo ++ [Node mn []]
  where lng = length fo

addElem といふのはリストに新たな要素を加へやうとしてゐる
Tree a といふ型のリストが Forest a と呼ばれるものだ
Forest に要素を加へていき showF でその内容をリストっぽく見せやうとしてゐる

Elm といふ型は加へたい要素の型と
「今まで加へた要素の最後のいくつを今回のものといっしょにまとめるか」「次に加へる要素のいくつを今回のものといっしょにまとめるか」といふ3つの情報を指定して要素を加へやうといふためのものだ
ちなみに最後の情報は別のコードから呼び出すときに使ふためのもので今回 ghciでは利用しない

かういふことをする場合このやうな「木」のデータ構造にする意義があるのではないかと思ふ

たとはばこのモジュールをghci で読みこんで

> a = addElem (El 1 0 0) []
> b = addElem (El 2 0 0) a
> c = addElem (El 3 0 0) b
> d = addElem (El 4 0 0) c
> e = addElem (El 5 2 0) d
> f = addElem (El 6 1 0) e

としたとき showF f は
"[1, 2, [3, 4, [5, 6]]]" となる