-4

Regarding How to elegantly represent finite Haskell recursive datastructure in Python?, I was thinking how would I represent an infinite data structure (without any non-constructor function inside it) from Haskell in Python using Haskell FFI.

Unfortunately I haven't found anything as elegant as was in this great this answer (JSON representation of finite structure) from leftaroundabout.

Is there any similarly elegant way to represent infinite data structure from Haskell to Python?

Přemysl Šťastný
  • 1,676
  • 2
  • 18
  • 39
  • 1
    Can you please include the relevant parts in the question itself? Also, the title and body ask a different question – which one are you interested in? – MisterMiyagi Feb 24 '22 at 14:43
  • @MisterMiyagi I don't see it. Can you be more specific please? – Přemysl Šťastný Feb 24 '22 at 14:48
  • 2
    But an infinite data structure in Haskell is *precisely* one with a function inside it (namely, a recursive call to a data constructor). For example, `ones = 1 : ones`. `ones` is a call to `(:)` with `ones` (a call to `(:)` with `ones` ...) as its second argument. – chepner Feb 24 '22 at 14:53
  • 1
    @chepner I didn't considered a data contrustor as a function. By no function a meant, there is nothing like (a -> b) inside the structure. – Přemysl Šťastný Feb 24 '22 at 14:55
  • 2
    when referring to other links, please write a summary of its content. the questions must make sense on its own -- others should not have to read all the linked information and still understand the questions as asked – LudvigH Feb 24 '22 at 14:58
  • 1
    @PřemyslŠťastný You should, because that's how "infinite" data structures are simulated (along with laziness); the data structure itself stores the continuation for generating the rest of it. I don't think that's something FFI can translate into Python (which would use generators to do something similar). – chepner Feb 24 '22 at 15:01
  • @LudvigH Is it better like it, or should I make longer summary? – Přemysl Šťastný Feb 24 '22 at 15:07
  • @chepner I know, that pure FFI probably can't do it itself. So I was thinking about passing some function which would operate on infinite datastructure to Python, but haven't found any elegant way, how to do it... - I am also concerned about generation of many pointers to functions via FFI. – Přemysl Šťastný Feb 24 '22 at 15:15
  • 2
    This question, like the one it links to, seems to be asking for an opinion-based thing. Please take some time to read [What type's of questions should I avoid asking](https://stackoverflow.com/help/dont-ask). Note, asking for "elegant" is useless, unless you define, in objective terms, what _you_ mean by "elegant". – TylerH Feb 24 '22 at 15:24
  • @TylerH Please, don't edit it like that. You changed the meaning of the question... This question is about infinite data structure, that before was about finite data structure. – Přemysl Šťastný Feb 24 '22 at 15:25
  • 1
    @PřemyslŠťastný I have not changed any references from infinite to finite, I have only removed opinion-based language or "thanks" noise. – TylerH Feb 24 '22 at 15:25
  • @TylerH No. I want simillary elegant way. Not better. It can't be better, because it is about different problem. – Přemysl Šťastný Feb 24 '22 at 15:27
  • 2
    @PřemyslŠťastný You don't seem to be understanding... it may be a language barrier issue. The word "elegant" in English means "pleasing or graceful", which is not an objective thing. The problem here is that what you consider elegant, I might consider **in**elegant. Objective things to ask might be "how can I do this without using X function" or "how can I do this without `foo`ing the `bar`?". Questions like "how can I do this in a more (or similarly) elegant way" are off-topic because they are opinion-based. – TylerH Feb 24 '22 at 15:29
  • 1
    @TylerH It is possible. I am using elegant as a direct short not hard to implement way. So you are saying, the elegant have different meaning in English then I thought? – Přemysl Šťastný Feb 24 '22 at 15:31
  • Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/242370/discussion-between-tylerh-and-premysl-sastny). – TylerH Feb 24 '22 at 15:32
  • 2
    I am thinking of a language barrier, too, but not involving English. Haskell and Python represent data structures *very* differently, and Python does not handle recursion well (which is critical to Haskell's representation of infinite data structures). I don't think it's possible to map from Haskell to Python in general. – chepner Feb 24 '22 at 15:33
  • 4
    Consider these two (relatively objective) "elegant" definitions, `ones = 1: ones` and `def make_ones(): while True: yield 1; ones = make_ones()`. There no obvious way to map one to the other, and that's before you get into crazy definitions like `fibs = 0 : 1 : zipWith (+) fibs (tail fibs)`. – chepner Feb 24 '22 at 15:36

2 Answers2

2

I suggest one of two routes.

  • Pass an opaque pointer to Python. Define an API in Haskell for observing and constructing things of the appropriate type, and expose that API through the FFI. (I also suggested this at the linked question...)
  • Explicitly construct graphs in the first place, and pass the graph structure to Python. For example, you could use data-reify to be able to do this while retaining the usual syntax for constructing and pattern matching on your custom types.
Daniel Wagner
  • 145,880
  • 9
  • 220
  • 380
  • I am aware of your first approach in the first question but it seemed to me too much clumsy in this situation...if I understand it right, it will generate possibly unlimited amount of new functions (exposed via pointers) during runtime and I am not sure, whether it is just a right way, how to do it. It seems to me as a really crazy solution for the problem, because I haven't seen yet any reasonable code doing this. - I will surely look at the second proposed solution. :-) – Přemysl Šťastný Feb 24 '22 at 23:12
  • @PřemyslŠťastný It shouldn't require an unlimited amount of new functions. Why would it? There should just be one set of functions for each type you want to share between your Haskell program and your Python program. – Daniel Wagner Feb 25 '22 at 00:11
  • I must think more about it, but very recklessly I imagine that vaguely on simple example of infinite list. Observation function would look like (f :: InfiniteList -> (elem, InfiniteList) ). And then there would have to be something made by Haskell FFI, which changes observation function into something more readable by C, something like function g0(), which just return struct x{ type elem; (*struct x)() g), where function g generates via Haskell FFI more and more functions with each new element you want to access via next g. - This is just my naive imagination. Please correct me, if I am wrong. – Přemysl Šťastný Feb 25 '22 at 00:27
  • On the second though, Haskell might just generete a function, which accepts a pointer to datastructure and returns the value and next pointer. Which variant is true please? – Přemysl Šťastný Feb 25 '22 at 00:33
  • On the third though, it is very improbable, that anybody implement Haskell FFI (I have never used it yet) in this functional way...so yes, you are probably right. Is it just about passing pointer to blackhole, which will be later evaluated by the function, and not passing the whole new function? – Přemysl Šťastný Feb 25 '22 at 00:41
  • 2
    @PřemyslŠťastný For example, for observations of an infinite `[Int]`, on the C side you might have something like `int head(void *)` and `void *tail(void *)`. – Daniel Wagner Feb 25 '22 at 01:39
  • Thanks. :-) - I didn't imagined it generates so simple API given the laziness...my thinking is sometimes over complicated. – Přemysl Šťastný Feb 25 '22 at 10:36
1

I think Auto-vivification provides an interesting way to create a recursive data structure. For python...

>>> class Tree(dict):
...     def __missing__(self, key):
...         value = self[key] = type(self)()
...         return value

>>> # Common names by class, order, genus, and type-species
>>> common_names = Tree()
>>> common_names['Mammalia']['Primates']['Homo']['H. sapiens'] = 'human being'
>>> common_names
{'Mammalia': {'Primates': {'Homo': {'H. sapiens': 'human being'}}}}

There is also a more compact implementation using defaultdict by Stephan

import collections

def Tree():
    return collections.defaultdict(Tree)
brocla
  • 123
  • 6