Sorting algorithms/Tree sort on a linked list: Difference between revisions

=={{header|Haskell}}==

Due to pure functional nature of Haskell sorting in situ is impossible.

Here we use abstractions of ``Foldable`` type class in order to traverse both the doubly-linked list and the binary tree.

Implementation of doubly-linked list is given here [[Doubly-linked_list/Traversal#Haskell]]

<lang haskell>{-# language DeriveFoldable #-}

import Data.Foldable

-- double-linked list

data DList a = End | Elem { prev :: DList a

, elt :: a

, next :: DList a }

mkDList :: Foldable t => t a -> DList a

mkDList = go End . toList

where go _ [] = End

go prev (x:xs) = current

where current = Elem prev x next

next = go current xs

instance Foldable DList where

foldMap f End = mempty

foldMap f dl = f (elt dl) <> foldMap f (next dl)

sortDL :: Ord a => DList a -> DList a

sortDL = mkDList . mkTree

-- binary tree

data BTree a = Empty | Node { left :: BTree a

, node :: a

, right :: BTree a }

deriving (Show, Foldable)

addTree Empty x = Node Empty x Empty

addTree (Node l a g) x =

case compare x a of

LT -> Node (addTree l x) a g

_ -> Node l a (addTree g x)

mkTree :: (Foldable t, Ord a) => t a -> BTree a

mkTree = foldl addTree Empty

treeSort :: (Foldable t, Ord a) => t a -> [a]

treeSort = toList . mkTree</lang>

<pre>λ> let l = mkDList [2,4,3,5,7,6,2,9]

λ> l

mkDList [2,4,3,5,7,6,2,9] :: Num a => DList a

λ> toList l

[2,4,3,5,7,6,2,9]

λ> mkTree l

Node {left = Empty, node = 2, right = Node {left = Node {left = Node {left = Empty, node = 2, right = Empty}, node = 3, right = Empty}, node = 4, right = Node {left = Empty, node = 5, right = Node {left = Node {left = Empty, node = 6, right = Empty}, node = 7, right = Node {left = Empty, node = 9, right = Empty}}}}}

λ> toList $ mkTree l

[2,2,3,4,5,6,7,9]

λ> toList $ sortDL l

[2,2,3,4,5,6,7,9]

λ> treeSort [2,4,3,5,7,6,2,9]

[2,2,3,4,5,6,7,9]</pre>