3 Replies - 6924 Views - Last Post: 29 February 2012 - 02:56 PM

#1 Alligator Jack  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 29-February 12

Functional implementation of String B-Trees

Posted 29 February 2012 - 06:15 AM

Hello guys,

do you happen to know if there's a functional implementation of String B-Trees out there?
I've been looking for them for a while but couldn't find one.
Preferably in SML, Haskell or F#.. but it really doesn't matter, as long as it's functional.

Have you ever worked with or heard of String B-Trees?

Thank you in advance,
Jack
Is This A Good Question/Topic? 0
  • +

Replies To: Functional implementation of String B-Trees

#2 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: Functional implementation of String B-Trees

Posted 29 February 2012 - 09:19 AM

you should read the paper "Purely functional data structures" it's in SML but the author adds hypothetical extensions(which are all available in Haskell) to make some of the structures possible. The same guy invented finger trees I believe.

languages like SML and Haskell actually lend themselves to trees quite well.

something like this.

data BTree a = Leaf a
             | Node BTree BTree


This post has been edited by ishkabible: 29 February 2012 - 09:22 AM

Was This Post Helpful? 0
  • +
  • -

#3 sepp2k  Icon User is online

  • D.I.C Lover
  • member icon

Reputation: 2100
  • View blog
  • Posts: 3,197
  • Joined: 21-June 11

Re: Functional implementation of String B-Trees

Posted 29 February 2012 - 09:41 AM

Quote

do you happen to know if there's a functional implementation of String B-Trees out there?


I don't think so (on the basis that if there were, it would probably show up on google).

View Postishkabible, on 29 February 2012 - 05:19 PM, said:

something like this.

data BTree a = Leaf a
             | Node BTree BTree



That's not a B-tree, let alone a string B-tree. That's a plain old binary tree.
Was This Post Helpful? 0
  • +
  • -

#4 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: Functional implementation of String B-Trees

Posted 29 February 2012 - 02:56 PM

O, I thought he meant binary tree of strings(like Set String). That is significantly different structure. sorry for the confusion(Still, "Purely functional data structures" is a really cool read although it doesn't cover BTrees it dose cover an extremely wide range of trees and sequences and the cost/benefits of various choices in functional languages).

This post has been edited by ishkabible: 29 February 2012 - 02:59 PM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1