Sorting algorithms/Tree sort on a linked list: Difference between revisions
Content added Content deleted
m (→{{header|Phix}}: made version consistent.) |
(→{{header|Haskell}}: added solution) |
||
Line 219: | Line 219: | ||
d c e b a -> a b c d e |
d c e b a -> a b c d e |
||
</pre> |
</pre> |
||
=={{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> |
|||
=={{header|J}}== |
=={{header|J}}== |