Anonymous user
Sorting algorithms/Tree sort on a linked list: Difference between revisions
Sorting algorithms/Tree sort on a linked list (view source)
Revision as of 08:27, 17 November 2021
, 2 years ago→{{header|Haskell}}: added solution
m (→{{header|Phix}}: made version consistent.) |
(→{{header|Haskell}}: added solution) |
||
Line 219:
d c e b a -> a b c d e
</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}}==
| |||