Haskell binary search tree with custom data

Question

I want to create a binary search tree of custom data type Book. Book has two attributes, name and page. I want to use attribute page as the node of the tree. I've stuck at defining the tree. Can anyone help me with any resource? Here is the code I've tried (it's not working)

import System.IO  
import Data.List  

data Book = Book{
    name:: String,
    page::Int
}deriving (Show)

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show, Read, Eq)

singleton :: (Book _ x) -> Tree x   
singleton (Book _ x) = Node x EmptyTree EmptyTree  

treeInsert :: (Ord a) => a -> Tree a -> Tree a  
treeInsert (Book _ x) EmptyTree = singleton (Book _ x)
treeInsert (Book _ x) (Node a left right)   
    | x == a = Node x left right  
    | x < a  = Node a (treeInsert (Book _ x) left) right  
    | x > a  = Node a left (treeInsert (Book _ x) right)

How are you stuck in defining the tree? You already defined the tree. — willeM_ Van Onsem
– willeM_ Van Onsem, Commented Nov 17, 2017 at 14:51
Your types are off. Book does not take a type variable, and singleton returns a Tree Int. — Zeta
– Zeta, Commented Nov 17, 2017 at 14:53
Do you want your Tree to hold only Books, or do you want it to hold any type? Right now, you are somewhere in between. — pat
– pat, Commented Nov 17, 2017 at 16:24

Federico Sawady · Accepted Answer · 2017-11-17 16:47:53Z

I recommend to you to use all the book entity and make and Ord instance for Book.

instance Eq Book where
    (Book _ n1) == (Book _ n2) = n1 == n2

instance Ord Book where
    (Book _ n1) > (Book _ n2) = n1 > n2

And change your code to this:

data Book = Book {
    name :: String,
    page :: Int
} deriving (Show)

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show, Read, Eq)

singleton :: a -> Tree a   
singleton x = Node x EmptyTree EmptyTree  

treeInsert :: (Ord a) => a -> Tree a -> Tree a  
treeInsert x EmptyTree = singleton x
treeInsert x (Node a left right)   
    | x == a = Node x left right  
    | x < a  = Node a (treeInsert x left) right  
    | x > a  = Node a left (treeInsert x right)

You will see that (Book _ n) is not a correct type, Book is.

And a will use values of any type to treeInsert since Book implements Ord.

pat · Accepted Answer · 2017-11-17 16:50:15Z

Maybe if we figure out the correct type signatures.

I presume you want the Tree to hold Books, ordered by page.

If we want Tree to hold only Book, we don't need to parameterize it. However, since you did parameterize Tree, let's assume that it can hold more than just Books.

In this case, we would expect:

singleton :: a -> Tree a
treeInsert :: Ord a => a -> Tree a -> Tree a

Where a could be Book, or any other appropriate type. However, in order for treeInsert to work with Book, we require Book to have an Ord instance.

The singleton function just puts the whole a into a Node:

singleton a = Node a EmptyTree EmptyTree

Note that Book does not appear in this definition since it is intended to work with all types.

The insertTree function will also not mention Book, but it will take advantage of the Ord instance it requires of its argument.

Edit

If you want Tree to work only with Book, then you should define it as:

data Tree = EmptyTree | Node Book Tree Tree

The type signatures for the functions then become:

singleton :: Book -> Tree
insertTree :: Book -> Tree -> Tree

The implementation of singleton will be the same as above (just put the whole Book into a Node).

Since insertTree now knows it is dealing with Book, it no longer requires the Ord instance, since it can just get the page.

It will start:

treeInsert b EmptyTree = singleton b
treeInsert b (Node a l r)
    | page b == page a = ...

Collectives™ on Stack Overflow

Haskell binary search tree with custom data

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related